Школяр Вася дуже допитливий і постійно шукає щось новеньке в Інтернеті. Зовсім нещодавно Васі гарно пофортунило - він знайшов \href{http://elementy.ru/lib/430178/430281}{відеолекцію} Арнольда, яку у той же вечір уважно передивився. На наступний день у школі на факультативі з програмування він придумав наступну задачку, яку і пропонує розв'язати Вам. Задано деяке не від'ємне ціле число - це перший член послідовності Арнольда. Тепер це число потрібно подати у двійковій системі числення і над отриманим бітовим поданням виконувати наступні операції: у наступному числі послідовності нове значення біта буде дорівнювати сумі поточного і наступного біта по модулю \textbf{2}. Так як у отаннього біта немає сусіда праворуч, то Вася для виконання операції дописував, за рекомендацією того ж Арнольда, у кінці знову перший біт. Вася з подивом помітив, що на деякому кроці отримана таким способом послідовність стає періодичною - здається і Арнольд щось про це також розплвідав, але Вася вже це точно не пам'ятає... Васю зацікавили такі питання: На якому кроці описаного вище алгоритму буде отримано перший член такої періодичної послідовності і яка довжина періоду цієї послідовності. Допоможіть Васі знайти відповіді на його запитання. \InputFile Єдине ціле невід'ємне число \textbf{n}, яке не перевищує \textbf{10^8}, - перший член послідовності. \OutputFile У єдиному рядку виведіть шуканих два числа, відокремлених пропуском: крок отримання першого періодичного члена такої періодичної послідовності і довжину періоду цієї послідовності.