Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

No tag edit access

The problem statement has recently been changed. View the changes.

×
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-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/19/2021 10:12:28 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|