For technical reasons, some programming languages (Kotlin, C #) will not be available during round 877.
×

No tag edit access

D. Rotatable Number

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBike 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·10^{6}, 2 ≤ *x* ≤ 10^{9}).

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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2017 21:59:13 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|