Бітова послідовність Арнольда
Школяр Вася дуже допитливий і постійно шукає щось новеньке в Інтернеті. Зовсім нещодавно Васі гарно пофортунило - він знайшов відеолекцію Арнольда, яку у той же вечір уважно передивився. На наступний день у школі на факультативі з програмування він придумав наступну задачку, яку і пропонує розв'язати Вам.
Задано деяке не від'ємне ціле число - це перший член послідовності Арнольда. Тепер це число потрібно подати у двійковій системі числення і над отриманим бітовим поданням виконувати наступні операції: у наступному числі послідовності нове значення біта буде дорівнювати сумі поточного і наступного біта по модулю 2. Так як у отаннього біта немає сусіда праворуч, то Вася для виконання операції дописував, за рекомендацією того ж Арнольда, у кінці знову перший біт. Вася з подивом помітив, що на деякому кроці отримана таким способом послідовність стає періодичною - здається і Арнольд щось про це також розплвідав, але Вася вже це точно не пам'ятає...
Васю зацікавили такі питання: На якому кроці описаного вище алгоритму буде отримано перший член такої періодичної послідовності і яка довжина періоду цієї послідовності. Допоможіть Васі знайти відповіді на його запитання.
Вхідні дані
Єдине ціле невід'ємне число n, яке не перевищує 10^8, - перший член послідовності.
Вихідні дані
У єдиному рядку виведіть шуканих два числа, відокремлених пропуском: крок отримання першого періодичного члена такої періодичної послідовності і довжину періоду цієї послідовності.