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>
using namespace std;
template <typename T>
void maxtt(T& t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T& t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int& x, int y, int mod = 998244353) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 998244353) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
long long mul(long long x, long long y, long long mo) {
  x %= mo;
  y %= mo;
  long long ans =
      (x * y - (long long)((long double)x * y / mo + 0.1) * mo) % mo;
  ans += ans < 0 ? mo : 0;
  return ans;
}
long long ksm(long long x, long long y, long long mo) {
  long long ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x, mo);
    x = mul(x, x, mo);
    y >>= 1;
  }
  return ans;
}
long long phi(long long x) {
  long long ans = x;
  for (long long i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      ans = ans / i * (i - 1);
      while (x % i == 0) x /= i;
    }
  }
  if (x > 1) ans = ans / x * (x - 1);
  return ans;
}
long long x, ans;
struct PollardRho {
  int times = 20;
  long long mul(long long a, long long b, long long mod) {
    long long ans = 0;
    while (b) {
      if (b & 1) {
        ans = (ans + a) % mod;
      }
      a = (a << 1) % mod;
      b >>= 1;
    }
    return ans;
  }
  long long pow(long long a, long long b, long long mod) {
    long long ans = 1;
    while (b) {
      if (b & 1) {
        ans = mul(ans, a, mod);
      }
      b >>= 1;
      a = mul(a, a, mod);
    }
    return ans;
  }
  bool witness(long long a, long long n) {
    long long temp = n - 1;
    int j = 0;
    while (temp % 2 == 0) {
      j++;
      temp /= 2;
    }
    long long x = pow(a, temp, n);
    if (x == 1 || x == n - 1) return 1;
    while (j--) {
      x = mul(x, x, n);
      if (x == n - 1) return 1;
    }
    return 0;
  }
  bool miller_rabin(long long n) {
    if (n == 2) return 1;
    if (n < 2 || n % 2 == 0) return 0;
    for (int i = 0; i < times; i++) {
      long long a = rand() % (n - 1) + 1;
      if (!witness(a, n)) return 0;
    }
    return 1;
  }
  long long pollard_gcd(long long a, long long b) {
    if (a == 0) return 1;
    if (a < 0) return pollard_gcd(-a, b);
    while (b) {
      long long t = a % b;
      a = b;
      b = t;
    }
    return a;
  }
  long long pollard_rho(long long n, long long c) {
    long long i = 1, k = 2;
    long long xx = rand() % n, y = xx;
    while (1) {
      i++;
      xx = (mul(xx, xx, n) + c) % n;
      long long d = pollard_gcd(y - xx, n);
      if (1 < d && d < n) return d;
      if (y == xx) return n;
      if (i == k) {
        y = xx;
        k <<= 1;
      }
    }
  }
  void find(long long n, vector<long long>& vp) {
    if (miller_rabin(n)) {
      vp.push_back(n);
      return;
    }
    long long p = n;
    while (p >= n) p = pollard_rho(p, rand() % (n - 1) + 1);
    find(p, vp);
    find(n / p, vp);
  }
} pro;
void cal(long long d) {
  long long md = lm / d;
  long long f = phi(md);
  long long miuD = phi(md);
  if (miuD == 1) {
    ans += f;
    return;
  }
  vector<long long> vp;
  pro.find(miuD, vp);
  for (long long z : vp) {
    while (miuD % z == 0 && ksm(x, miuD / z, md) == 1) miuD /= z;
  }
  assert(f % miuD == 0);
  ans += f / miuD;
}
void fmain(int ID) {
  scanf("%lld%lld", &lm, &x);
  for (long long i = 1; i * i <= lm; i++)
    if (lm % i == 0) {
      cal(i);
      if (i * i != lm) cal(lm / i);
    }
  printf("%lld\n", ans);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}