Байк — это умный мальчик, он обожает математику. Находясь под впечатлением от числа 142857, он изобрел числа, которые назвал «вращаемые числа».

Как можно видеть, 142857 — это волшебное число, так как любой его циклический сдвиг можно получить, умножая это число на числа 1, 2, ..., 6 (числа от 1 до длины числа). Циклический сдвиг числа получается, если поставить несколько его последних цифр на первое место. Например, сдвигая число 12345, можно получить любое из следующих чисел: 12345, 51234, 45123, 34512, 23451. Стоит отметить, что ведущие нули разрешены. Таким образом, как 4500123, так 0123450 можно получить, сдвигая 0012345. Можно видеть, почему 142857 удовлетворяет условию. Все 6 равенств записаны в 10-тичной системе счисления:

• 142857·1 = 142857;
• 142857·2 = 285714;
• 142857·3 = 428571;
• 142857·4 = 571428;
• 142857·5 = 714285;
• 142857·6 = 857142.

Байк придумал себе задачу. Он пробует создать «вращаемое число» для любой системы счисления. Выше уже упоминалось, что 142857 — это 10-ичное «вращаемое число». Еще один пример — двоичное число 0011. Все 4 уравнения записаны в 2-ичной системе счисления.

• 0011·1 = 0011;
• 0011·10 = 0110;
• 0011·11 = 1001;
• 0011·100 = 1100.

Итак, Байк хочет найти максимальное b (1 < b < x), такое, чтобы существовало положительное «вращаемое число» (ведущие нули разрешены) длины n в b-ичной системе счисления.

Обратите внимание, что каждый раз, когда вы умножаете «вращаемое число» на число от 1 до длины этого числа, вы должны получать циклический сдвиг этого числа.