D2 - Bláznivá matematikárka

Dobrých učiteľov je málo, a preto si ich ceňte!

Napríklad taká Monika je úplne bláznivá matematikárka. Svojim žiakom dá každý deň nejakú nezmyselnú domácu úlohu, s ktorou si potom celé popoludnie bezradne lámu hlavu.

Dnes dostali Monikini žiaci za úlohu nájsť k zadanému číslu najbližšie väčšie číslo, ktoré má rovnaký ciferný súčet (našťastie len v desiatkovej sústave). A aby to nemali také jednoduché a nebodaj na domácej úlohe nespolupracovali, dala Monika každému žiakovi iné číslo, s ktorým má pracovať.

Jediné šťastie je, že medzi spolužiakmi majú aj vás – a ak sa s vami podelia o zajtrajšiu desiatu, možno im napíšete program, ktorý výsledok rýchlo zráta pre každého z nich.

Vstup

Na prvom riadku vstupu je počet spolužiakov P (1 ≤ P ≤ 100). Každý z nasledujúcich P riadkov obsahuje jedno kladné celé čislo n, ktoré zadala Monika niektorému spolužiakovi.

D1

1 ≤ n ≤ 100 000

D2

1 ≤ n ≤ 10¹⁰⁰

Výstup

Pre každé číslo zo vstupu vypíšte jeden riadok obsahujúci najbližšie väčšie číslo, ktoré má rovnaký ciferný súčet ako pôvodné číslo.

Príklad

Vstup:

3
9
10
11

Výstup:

18
100
20