5. Všetko so všetkým súvisí

Anička rada hľadá súvislosti medzi rôznymi vecami - napríklad medzi počtom ľudí v autobuse a jeho meškaním, medzi klimatickým stavom podnebia a kvalitou sobej pečienky, medzi časom stráveným na záchode a počtom bodov v Olympiáde v informatike, medzi časom stráveným na záchode a počtom bodov z písomky z dejepisu… a takto by sme mohli pokračovať ďalej.

V poslednej dobe Anička začala skúmať ciferné súčty a uvedomila si, že číslo a jeho ciferný súčet zvyčajne spolu nijak nesúvisia ¹. Napríklad by sa jej páčilo, keby bolo číslo svojím ciferným súčtom deliteľné. Hľadať takéto čísla je však vcelku namáhavé, a preto by Anička bola rada, keby ste jej napísali program na ich hľadanie.

Úloha

Vašou úlohou je pre dané prirodzené číslo \(n\) nájsť také prirodzené číslo, ktoré má ciferný súčet rovný \(n\) a je ním aj deliteľné. Navyše, aby Aničke neprišlo zle z priveľkých čísel, nájdite najmenšie také číslo. Môžete predpokladať, že riešenie vždy existuje.

Formát vstupu

Na jedinom riadku vstupu je dané celé číslo \(1 \leq n \leq 1000\).

Formát výstupu

Vypíšte jediný riadok a na ňom jediné prirodzené číslo – najmenšie číslo s ciferným súčtom \(n\), ktoré je týmto ciferným súčtom aj deliteľné. Upozorňujeme, že výsledné číslo môže byť veľmi veľké a nemusí sa vojsť ani do \(64\)-bitovej celočíselnej premennej.

Hodnotenie

Sú štyri sady vstupov, za každú možno získať \(2\) body. Maximálne hodnoty \(n\) v jednotlivých sadách sú postupne \(20\), \(50\), \(200\) a \(1000\).

Príklady

Input:

4

Output:

4

Input:

11

Output:

209

\(2+0+9=11\) a \(209/11=19\), čo je celé číslo.

Input:

81

Output:

999999999