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