Problem description

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 1² + 2² + 3² = 1 + 4 + 9 = 14, by później być zamienioną w 1² + 4² = 1 + 16 = 17, a potem w 1² + 7² = 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 ≤ 10¹⁸.

Przykład

123

4

13

1

11

2