D. Вращаемое число
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Байк — это умный мальчик, он обожает математику. Находясь под впечатлением от числа 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 до длины этого числа, вы должны получать циклический сдвиг этого числа.

Входные данные

В единственной строке записано два целых числа через пробел n, x (1 ≤ n ≤ 5·106, 2 ≤ x ≤ 109).

Выходные данные

Выведите единственное целое число — максимальное b. Если такого b не существует, выведите вместо этого -1.

Примеры
Входные данные
6 11
Выходные данные
10
Входные данные
5 8
Выходные данные
-1