T'has parat a pensar mai perquè comptem fent servir 10 dígits?

Doncs és molt probable que sigui per la mateixa raó que si hagués estat el Hommer Simpson el responsable de crear el sistema de numeració, comptariem fent servir només 8 dígits.

Tot depèn del nombre de dits que tenim. Les civilitzacions antigues, com els nens petits, feien servir els dits per comptar. Però comptar amb els dits ens serveix per quantitats petites i no és senzill fer operacions matemàtiques. En cal un sistema de representació i el més senzill és que tingui tants símbols com dits fem servir.

Els sistemes de representació actuals ténen una cosa en comú: fan servir prioritàriament els dígits del 0 al 9 i, si calen més símbols, fan servir lletres majúscules des de l'A fins a la Z (fent servir únicament caràcters de l'alfabet anglès).

Entrada

La primera línia conté un enter N amb el nombre de casos a tractar.

A continuació venen N línies amb un número X (representat amb 10 simbols) seguida d'un nombre enter D ( 2 <= D <= 36) que indica la quantitat de dígits que farem servir.

Sortida

Per cada cas cal indicar com es representa el número X si tinguessim D simbols per representar-lo.

Exemple d'entrada

4
7 10
7 2
7 3
123412 30

Exemple de sortida

7
111
21
4H3M