B1 - Dopravné značky

Ali je veľký cestovateľ, ktorý rád navštevuje kadejaké zvláštne krajiny. Pred rokom napríklad navštívil krajinu, kde tamojšie Ministerstvo dopravy zaviedlo mimoriadne šetrné opatrenie: Rozhodli sa ušetriť na dopravných značkách – konkrétne na značkách, ktoré informujú vodiča o počte zostávajúcich kilometrov do cieľa cesty. Na nastriekanie číselného údaja na každú takúto značku použili vždy len maximálne 2 rôzne šablóny číslic.

Našťastie je finančná kríza už na ústupe, a aj rozpočet Ministerstva dopravy je tento rok o niečo väčší. Rozhodlo sa teda šetrné opatrenia zmierniť – od nového roka môžu byť na výrobu jednej dopravnej značky použité až tri rôzne šablóny číslic.

Úloha

Ali sa nachádza vo vzdialenosti X kilometrov od svojho cieľa. Za predpokladu, že značky sú umiestnené na každom kilometri, ktorý obsahuje najviac tri rôzne cifry, určte dopravnú značku, ktorú Ali stretne ako prvú.

Vstup

Prvý riadok vstupu obsahuje kladné celé číslo N určujúce počet testovacích sád (1 ≤ N ≤ 1000). Každý z nasledujúcich N riadkov obsahuje jedno kladné celé číslo X určujúce počet kilometrov ostávajúcich do cieľa cesty (2 ≤ X).

Výstup

Pre každé číslo X zo vstupu vypíšte najväčšie číslo menšie ako X, ktorého ciferný zápis obsahuje najviac tri rôzne cifry.

B1

1 < X ≤ 999 999

B2

Každé z čísel na vstupe je väčsie ako 1 a má najviac 10 000 cifier.

Príklad

Vstup:

6
1568
6894
1231
8
123456
100

Výstup:

1566
6889
1229
7
123333
99