Bike是一个聪明的男孩,非常热爱数学。他受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.
现在,自行车有问题。他将“可旋转数”扩展到任何基数下 b.如上所述,142857 是基数 10 下的“可旋转数”。另一个例子是基数 2 下的 0011。所有 4 个方程都在基数 2 下。
- 0011·1 = 0011;
- 0011·10 = 0110;
- 0011·11 = 1001;
- 0011·100 = 1100.
因此,他想要找到最大的 b (1 < b < x),以便在基数 b 下存在长度为 n 的正“可旋转数”(允许有前导零)。
请注意,每当将可旋转数字乘以从 1 到其长度的数字时,您都应该得到该数字的旋转。
输入
唯一一行包含两个空格分隔的整数 n, x (1 ≤ n ≤ 5·106, 2 ≤ x ≤ 109)。
输出
打印一个整数——你找到的最大的 b。如果不存在这样的 b,则打印 -1。
示例
输入 #1
6 11
输出 #1
10
输入 #2
5 8
输出 #2
-1