eolymp
bolt
Try our new interface for solving problems
Məsələlər

Битовая последовательность Арнольда

Битовая последовательность Арнольда

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Школьник Вася очень любознательный и постоянно ищет что-то новое в Интернете. Совсем недавно Васе крупно повезло - он нашел видеолекцию Арнольда, которую в тот же вечер внимательно просмотрел. На следующий день в школе на факультативе по программированию он придумал следующую задачку, которую и предлагает решить Вам.

Дано некоторое не отрицательное целое число - это первый член последовательности Арнольда. Теперь это число нужно представить в двоичной системе счисления и над полученным битовым представлением производить следующие операции: в следующем числе последовательности новое значение бита будет равно сумме этого и последующего бита по модулю 2. Так как у последнего бита нет соседа справа, то Вася для выполнения операции приписывал, по рекомендации того же Арнольда, в конце опять первый бит. Вася с удивлением заметил, что на некотором шаге получаемая таким способом последовательность становится периодической - кажется и Арнольд что-то об этом тоже рассказывал, но Вася уже это точно не помнит...

Васю заинтересовали такие вопросы: На каком шаге описанного выше алгоритма будет получен первый член такой периодической последовательности и какова длина периода этой последовательности. Помогите Васе найти ответы на его вопросы.

Giriş verilənləri

Единственное целое неотрицательное число n, не превышающее 10^8, - первый член последовательности.

Çıxış verilənləri

В единственной строке выведите искомых два числа, разделённые пробелом: шаг получения первого периодического члена такой периодической последовательности и длину периода этой последовательности.

Nümunə

Giriş verilənləri #1
21
Çıxış verilənləri #1
2 15