CF303D.Rotatable Number

Bike is a smart boy who loves math very much. He invented a number called "Rotatable Number" inspired by $142857$ .

As you can see, $142857$ is a magic number because any of its rotatings can be got by multiplying that number by $1,2,...,6$ (numbers from one to number's length). Rotating a number means putting its last several digit into first. For example, by rotating number $12345$ you can obtain any numbers: $12345,51234,45123,34512,23451$ . It's worth mentioning that leading-zeroes are allowed. So both $4500123$ and $0123450$ can be obtained by rotating $0012345$ . You can see why $142857$ satisfies the condition. All of the $6$ equations are under base $10$ .

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

Now, Bike has a problem. He extends "Rotatable Number" under any base $b$ . As is mentioned above, $142857$ is a "Rotatable Number" under base $10$ . Another example is $0011$ under base 2. All of the $4$ equations are under base $2$ .

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

So, he wants to find the largest $b$ (1<b<x) so that there is a positive "Rotatable Number" (leading-zeroes allowed) of length $n$ under base $b$ .

Note that any time you multiply a rotatable number by numbers from 1 to its length you should get a rotating of that number.

The only line contains two space-separated integers $n,x$ $(1<=n<=5·10^{6},2<=x<=10^{9})$ .

Print a single integer — the largest $b$ you found. If no such $b$ exists, print -1 instead.