Problem description

Rozważmy cechę podzielności przez 11:

• pogrupuj cyfry liczby na grupy po dwie cyfry (poczynając od końca liczby) (na przykład dla liczby 1361646 pogrupowanie wygląda następująco: 1, 36, 16, 46),
• oblicz sumę uzyskanych grup (w powyższym przypadku 1 + 36 + 16 + 46 = 99),
• liczba jest podzielna przez 11 wtedy i tylko wtedy, gdy uzyskana suma grup jest podzielna przez 11.

Okazuje się, że istnieją analogiczne cechy podzielności przez inne liczby. Na przykład cecha podzielności przez 37 wygląda tak samo, z tym, że dzielić należy na grupy po trzy cyfry (i oczywiście zamiast sprawdzać podzielność sumy przez 11 należy dzielić przez 37). Jeszcze innym przykładem jest podzielność przez 3, gdzie wystarczy dzielić na grupy jednocyfrowe.

Celem tego zadania jest rozwiązanie zagadki wyznaczenia analogicznej cechy podzielności przez dowolną liczbę pierwszą N.

Napisz program, który: wczyta N, wyznaczy najmniejsze dodatnie r, że cecha podzielności przez N polega na podzieleniu liczby N na grupy po r cyfr, obliczenie ich sumy i sprawdzenie podzielności sumy przez N i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (i jedynym) wierszu wejścia znajduje się jedna liczba naturalna N.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć szukana liczba r. Jeśli taka liczba nie istnieje (nie istnieje analogiczna cecha podzielności dla zadanego N) – należy wypisać jedno słowo NIE.

Ograniczenia

1 ≤ N ≤ 10¹². Liczba N jest pierwsza.

Przykład

11

2

37

3

3

1

5

NIE