Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

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.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 06:38:06 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|