Problem: The campus has m rooms numbered from 0 to m - 1. Also the x-mouse lives in the campus. The x-mouse is not just a mouse: each second x-mouse moves from room i to the room i ⋅ x mod{m} (in fact, it teleports from one room to another since it doesn't visit any intermediate room). Starting position of the x-mouse is unknown.

You are responsible to catch the x-mouse in the campus, so you are guessing about minimum possible number of traps (one trap in one room) you need to place. You are sure that if the x-mouse enters a trapped room, it immediately gets caught.

And the only observation you made is GCD (x, m) = 1.

Input

The only line contains two integers m and x (2 ≤ m ≤ 10^{14}, 1 ≤ x < m, GCD (x, m) = 1) — the number of rooms and the parameter of x-mouse. 

Output

Print the only integer — minimum number of traps you need to install to catch the x-mouse.

Examples

Input

4 3


Output

3


Input

5 2


Output

2

Note

In the first example you can, for example, put traps in rooms 0, 2, 3. If the x-mouse starts in one of this rooms it will be caught immediately. If x-mouse starts in the 1-st rooms then it will move to the room 3, where it will be caught.

In the second example you can put one trap in room 0 and one trap in any other room since x-mouse will visit all rooms 1..m-1 if it will start in any of these rooms.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
const long long N = 1000005;
long long m, a[N], f[N], p[N], n, cnt, x, ans;
std::map<long long, long long> id;
std::vector<long long> v;
void init() {
  for (long long i = 1; i * i <= m; i++)
    if (m % i == 0) {
      a[++n] = i;
      if (m / i != i) a[++n] = m / i;
    }
  std::sort(a + 1, a + n + 1);
  for (long long i = 1; i <= n; i++) id[a[i]] = i;
  long long x = m;
  for (long long i = 2; i * i <= x; i++) {
    if (x % i) continue;
    p[++cnt] = i;
    while (x % i == 0) x /= i;
  }
  if (x > 1) p[++cnt] = x;
  for (long long i = 1; i <= n; i++) f[i] = m / a[i];
  for (long long i = 1; i <= cnt; i++)
    for (long long j = 1; j <= n; j++)
      if (a[j] % p[i] == 0) f[id[a[j] / p[i]]] -= f[j];
}
long long mul(long long x, long long y, long long mu) {
  x %= mu;
  y %= mu;
  long long ans = (x * y - (long long)((double)x * y / mu + 0.1) * mu) % mu;
  ans += ans < 0 ? mu : 0;
  return ans;
}
long long ksm(long long x, long long y, long long mu) {
  long long ans = 1;
  x = x % mu;
  for (; y; y >>= 1, x = mul(x, x, mu))
    if (y & 1) ans = mul(x, ans, mu);
  return ans;
}
bool MR(long long n) {
  if (n == 2 || n == 3 || n == 5 || n == 7) return 1;
  if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return 0;
  long long T = 12;
  long long d = n - 1, k = 0;
  while (d % 2 == 0) d >>= 1, k++;
  while (T--) {
    long long x = rand();
    x = ksm(x, d, n);
    if (x == 0) continue;
    for (long long i = 1; i <= k; i++) {
      long long t = x;
      x = mul(x, x, n);
      if (x == 1 && (t != 1 && t != n - 1)) return 0;
    }
    if (x != 1) return 0;
  }
  return 1;
}
long long gcd(long long x, long long y) {
  if (x % y == 0) return y;
  return gcd(y, x % y);
}
long long PR(long long n) {
  if (n % 2 == 0) return 2;
  if (n % 3 == 0) return 3;
  long long x = rand(), y = x, c = 12, step = 0, t = 1;
  while (++step) {
    y = (mul(y, y, n) + c) % n;
    if (x == y) return n;
    long long g = gcd((y - x + n) % n, n);
    if (g > 1) return g;
    if (step == t) x = y, t <<= 1;
  }
}
void find(long long n) {
  if (n == 1) return;
  if (MR(n)) {
    v.push_back(n);
    return;
  }
  long long d = n;
  while (d == n || d == 1) d = PR(n);
  while (n % d == 0) n /= d;
  find(d);
  find(n);
}
signed main() {
  srand(time(0));
  scanf("%lld%lld", &m, &x);
  init();
  for (long long i = 1; i < n; i++) {
    long long t = m / a[i], c = f[id[a[i]]];
    v.clear();
    find(c);
    std::sort(v.begin(), v.end());
    std::unique(v.begin(), v.end());
    for (auto j : v)
      while (c % j == 0 && ksm(x, c / j, t) == 1) c /= j;
    ans = ans + f[i] / c;
  }
  printf("%lld\n", ans + 1);
}