Vladko je masívny podnikateľ, ktorý vlastní obrovské pole. Nemá ale čas ho sám poorať. Preto si zavolal Merlina z ďalekej Prahy aby mu ho pooral. Merlina fakt baví orať polia. Robí to už od malička, takže nemal čas chodiť do školy ani naučiť sa počítať v desiatkovej sústave. Keď Merlin dooral, napísal na papier koľko metrov štvorcových pooral v nejakej číselnej sústave a to odovzdal Vladkovi. Vladko Merlina silno podceňuje a ani nemá poňatia v akej sústave to je, tak chce zisťiť, koľko najmenej metrov štvorcových to mohlo byť.

Úloha

Na vstupe dostanete postupnosť symbolov. Táto postupnosť reprezentuje číslo. Každý symbol reprezentuje jednu cifru a rovnaké cifry reprezentujú rovnaké cifry. Napríklad postupnosť abcdcdd môže znamenať $8264644_9$ v deviatkovej sústave čo je $4412434_{10}$ v desiatkovej sústave alebo $2351511_6$ v šestkovej sústave čo je $123523_{10}$ v desiatkovej sústave. Vašou úlohou bude zistiť aké najmenšie čislo to mohlo byť a vypísať ho v desiatkovej sústave. Ďalej ešte viete, že Merlin nepoužíva jednotkovú sústavu a číslo sa nezačína nulami.

Formát vstupu

V prvom riadku vstupu je číslo $t$ ($1 \leq t \leq 10^4$) udávajúce počet postupností.

Potom nasleduje $t$ riadkov. Na každom riadku je jedna postupnosť nanajvýš $l$ symbolov $a_i$ (symboly sú malé a veľké písmená anglickej abecedy a cifry 0 až 9).

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíš $t$ riadok, na každom bude najmenšie číslo, ktoré mohla postupnosť znakov reprezentovať v desiatkovej sústave.

Príklad

Input:

3
Ab
mama
r3Kt

Output:

2
10
75

Prvá postupnosť bude reprezentovať $10_2$, čiže $2_{10}$. Druhá postupnosť bude reprezentovať $1010_2$, čiže $10_{10}$. Tretia postupnosť bude reprezentovať $1023_4$, čiže $75_{10}$ – všimnite si, že aj cifry môžeme nahradiť.