На планете Фарале ходят инопланетяне с B руками. Исследователь Митофей скрупулёзно изучает их язык и систему записи чисел. Как вы уже догадались, все числа на Фарале записываются в B-ичной системе счисления. Несмотря на это, даже фараляне понимают ценность двоичной системы счисления, ведь не так давно был собран первый на их планете компьютер! Да, он ещё громоздкий, но зато умеет складывать числа! Причём не просто так, а используя побитовое исключающее «ИЛИ»! Так и написано в инструкции!

К сожалению, Митофей ещё не до конца разобрался в языке фараляней. Поэтому, когда он пролистывал инструкцию и обнаружил функцию συναριθμo(x), он перевёл её описание так: «συναριθμo(x) — означает сумму суммы цифр и побитового исключающего «ИЛИ» цифр. Например, в десятичной системе счисления συναριθμo(12₁₀) = (1 + 2) + (1 ⊕ 2) = 6₁₀, συναριθμo(26₁₀) = (2 + 6) + (2 ⊕ 6) = 12₁₀, а в троичной системе счисления συναριθμo(202₃) = (2 + 0 + 2) + (2 ⊕ 0 ⊕ 2) = 11₃». Примеры Митофей дописал сам, ведь прикасаться к компьютеру ему запретили.

Нетрудно заметить, что συναριθμo(x) принимает любое положительное целое число в B-ичной системе счисления и возвращает положительное целое число в B-ичной системе счисления. Митофея заинтересовал один вопрос: что произойдёт, если подставить в функцию результат её выполнения? А затем ещё раз, и ещё раз, и так до бесконечности? Понятно, что для некоторых чисел в какой-то момент мы получим результат, который мы уже раньше встречали. Иными словами, мы зациклились. Назовём длиной цикла, содержащего x, такое минимальное целое число k, что συναριθμo^k(x) = x. Найдите длину наибольшего цикла.

В единственной строке даётся целое число B — основание системы счисления на планете Фарале (3 ≤ B ≤ 10¹²).

Выведите длину наибольшего цикла функции συναριθμo(x).