2. Orať je zábava

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ť.