eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Вася проти Деліня

Вася проти Деліня

Ліміт часу 20 секунд
Ліміт використання пам'яті 64 MiB

Як Ви вже знаєте з задачі "Бітова послідовьність Арнольда", школяр Вася дуже допитливий і постійно шукає щось новеньке в Інтернеті. Зовсім нещодавно Васі дуже повезло - він знайшов відеолекцію Арнольда, яку у той же вечір уважно переглянув. Наступного дня у школі на факультативі з програмування він придумав наступну задачку, яку і пропонує розв'язаити Вам.

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

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

Допоможіть Васі швидко знаходити відповіді на подобні запити.

Вхідні дані

У кожному рядку вхідного файлу знаходиться єдине ціле невід'ємне число n, яке не перевищує 10^10, - перший член послідовності.

Вихідні дані

Для кожного запиту, отриманого на вході, у окремому рядку виведіть шуканих два числа, відокремлені пропуском: крок отримання першого періодичного члена такої періодичної послідовності та довжину періода цієї послідовності.

Приклад

Вхідні дані #1
21
10000000000
3
2753
1753
Вихідні дані #1
2 15
3 510
2 1
5 3
2 341