Задача C. Вычеркивание чисел ≡

Условие

В Научно-исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его сотрудники открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать.

Сегодня Тимофею ничего научного не приходит в голову. Чтобы окружающие не заподозрили его в бездеятельности, он вычеркивает некоторые числа из бесконечного ряда натуральных чисел. Делает он это, впрочем, не хаотично, а по определенным правилам.

На первом шаге он вычеркнул каждое второе натуральное число. На втором шаге из оставшихся чисел он вычеркнул каждое третье число. На третьем шаге из оставшихся чисел он вычеркнул каждое четвертое число, и так далее.

Попробуйте определить, на каком шаге Тимофей вычеркнет своё любимое число n.

Формат входных данных

Единственная строка входного файла содержит натуральное число n.

Формат выходных данных

Выведите одно натуральное число — на каком шаге будет вычеркнуто число n. Если оно не будет вычеркнуто никогда, выведите число -1.

Ограничения

1 ≤ n ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 10⁶, получат не менее 60 баллов.

Пояснение к примерам

В первом примере n = 15. Исходный ряд натуральных чисел:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ...

После первого шага Тимофей вычеркнет каждое второе число, то есть останутся только нечетные числа:

1 3 5 7 9 11 13 15 17 19 21 ...

После второго шага Тимофей вычеркнет каждое третье оставшееся число:

1 3 7 9 13 15 19 21 ...

После третьего шага Тимофей вычеркнет каждое четвертое оставшееся число:

1 3 7 13 15 19 ...

После четвертого шага Тимофей вычеркнет каждое пятое оставшееся число:

1 3 7 13 19 ...

Любимое число вычеркнуто на четвертом ходу.

Во втором примере n = 19. Оно не будет вычеркнуто никогда: после четвертого шага будут вычеркиваться только числа, больше, чем 19.

Примеры тестов

15

4

19

-1