303_D. Rotatable Number_9660
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
#include <bits/stdc++.h>
using namespace std;
long long pp;
int n, x, pr[110000];
long long mo(long long a) {
  if (a >= 0 && a < pp) return a;
  a %= pp;
  if (a < 0) a += pp;
  return a;
}
long long ksm(long long a, int b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = mo(ans * a);
    a = mo(a * a);
    b /= 2;
  }
  return ans;
}
void fenjie(int n) {
  for (int i = 2; i <= n; i++)
    if (n % i == 0) {
      pr[++pr[0]] = i;
      while (n % i == 0) n /= i;
    }
}
int main() {
  cin >> n >> x;
  for (int i = 2; i * i <= n + 1; i++)
    if ((n + 1) % i == 0) {
      printf("-1\n");
      return 0;
    }
  fenjie(n);
  pp = n + 1;
  for (int i = x - 1; i > 1; i--) {
    bool ok = 1;
    for (int j = 1; j <= pr[0]; j++)
      if (ksm(i, n / pr[j]) == 1) {
        ok = 0;
        break;
      }
    if (ok) {
      printf("%d\n", i);
      return 0;
    }
  }
  printf("-1\n");
  return 0;
}

6 11
 5 8
 1 2
 4565598 65243634
 100 3661
 4989580 580108834
 4806718 719228528
 4850940 1249925
 91 6579
 4885608 36
 4554552 52
 4819162 628442864
 4958188 50573541
 4584690 111221963
 96 226573140
 4659468 326432989
 100 998579551
 4637782 744272977
 4708386 739015039
 1000033 987654321
 96 7815
 4597694 3729016
 4819150 1023221
 4929388 408412310
 96 951753385
 100 935250127
 100 3257
 1 100
 4584720 292130
 4950138 943842183
 4675062 317110372
 4644832 2
 4765486 2843533
 1000002 10000000
 4717098 77887266
 4818060 238135431
 4927750 67567983
 4785600 847746219
 4827750 360496418
 4571442 2
 4935742 3393126
 4766386 4
 96 201636768
 100 2
 4605448 125177681
 96 8688
 4820422 270513305
 4677246 515729434
 4980752 887319973
 4561488 973846429
 4781760 695269412
 93 115188153
 96 4
 4935012 726123193
 4644952 261468430
 96 9561
 4565598 32958137
 110 3661
 4958188 82835807
 4584690 195027413
 96 86315460
 100 758264491
 4637782 345546443
 4819150 1473059
 96 1621010723
 4675062 627310126
 4818060 42714226
 4785600 724910488
 4827750 195074331
 4935742 1491796
 96 15806
 4677246 377488151
 4561488 1054771903
 36 115188153
 96 5640
 4584690 92811203
 100 361090755
 2020611 580108834
 2640067 719228528
 33 6579
 4273968 36
 286950 52
 1962189 326432989
 1736748 987654321
 74 7815
 4597694 2844637
 4929388 719055056
 110 935250127
 3875240 292130
 1337619 2843533
 1775459 10000000
 4250045 67567983
 55 201636768
 2945063 695269412
 154 4
 2683973 261468430
 11 11
 5 10
 445651 32958137
 2020611 496945188
 2640067 106486079
 33 12748
 1068261 36
 207341 52
 4384902 82835807
 107 86315460
 2479516 326432989

10
 -1
 -1
 65243602
 3654
 580108807
 719228500
 1249882
 -1
 -1
 -1
 628442844
 50573516
 111221906
 226573126
 326432950
 998579544
 744272957
 739015006
 -1
 7801
 -1
 1023185
 -1
 951753371
 935250120
 3250
 99
 292083
 943842145
 317110324
 -1
 2843506
 9999997
 77887234
 238135373
 67567954
 847746176
 360496372
 -1
 3393099
 2
 201636754
 -1
 125177650
 8674
 270513285
 515729391
 -1
 973846392
 695269366
 -1
 -1
 726123159
 261468404
 9547
 32958135
 -1
 82835803
 195027412
 86315457
 758264487
 345546442
 1473058
 1621010721
 627310118
 42714225
 724910485
 195074326
 1491793
 15804
 377488150
 1054771900
 115188146
 5639
 92811202
 361090754
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
