MOG
Spanish
|
English

Matcom Online Grader

MOG Round #22

Ended

G - Anagramas

Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

Un anagrama de una cadena de caracteres es cualquier cadena formada por los mismos caracteres que la original (una cadena es anagrama de si misma). Por ejemplo, la cadena “MOG” tiene 6 anagramas, dados en orden alfabético: { GOM, GMO, MGO, MOG, OGM, OMG }. Como otro ejemplo, la cadena “ICPC” tiene 12 anagramas (en orden alfabético): { CCIP, CCPI, CICP, CIPC, CPCI, CPIC, ICCP, ICPC, IPCC, PCCI, PCIC, PICC }. Dado una cadena s y un entero k , tu tarea consiste en determinar su k-ésimo anagrama en el orden alfabético (de sus anagramas, por supuesto).

Input

En la primera línea de la entrada, un entero n — la cantidad de casos. En las siguiente n líneas una cadena s , formada por letras mayúsculas, y de longitud a lo sumo 20; seguida de un entero k . El valor de k estará en el rango de 1 a la cantidad de anagramas distintos de s .

Output

Por cada caso una línea con el k-ésimo anagrama de cada palabra.

Sample test(s)

Input
2 MOG 5 ICPC 12
Output
OGM PICC

Hints

Hints
Utilice enteros de 64 bits para realizar los cálculos.