Problem3222--Rotatable Number

3222: Rotatable Number

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

The only line contains two space-separated integers n,x (1≤n≤5·106,2≤x≤109).

Output

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

Examples
Input
6 11
Output
10
Input
5 8
Output
-1

Source/Category