Problem description


Dziwny proces liczbowy
(proces-liczbowy)
Memory limit: 32 MB
Time limit: 1.00 s

Jasio ma liczbę naturalną N. Postanowił wielokrotnie wykonać na swojej liczbie następujący proces: zamienić ją na sumę kwadratów jej cyfr. Na przykład: liczba 123 zostanie zamieniona na 12 + 22 + 32 = 1 + 4 + 9 = 14, by później być zamienioną w 12 + 42 = 1 + 16 = 17, a potem w 12 + 72 = 1 + 49 = 50. Jasio wykonuje ten proces i wykonuje i w sumie to już mu się nudzi powoli, ale zastanawia się jaką najmniejszą liczbę w skutek wykonywania swojego (nieskończonego) procesu otrzyma. Pomóż mu!

Napisz program, który: wczyta liczbę naturalną N, wyznaczy najmniejszą liczbę naturalną, która powstaje w wyniku nieskończonego procesu Jasia i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna N – liczba, od której rozpoczyna Jasio.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna – minimalna liczba jaką może uzyskać Jasio w wyniku wykonywania swojego procesu.

Ograniczenia

1 ≤ N ≤ 1018.

Przykład

Input Output
123
4
Input Output
13
1
Input Output
11
2