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;
unsigned int seed;
unsigned int getrand() {
  seed ^= seed << 13;
  seed ^= seed >> 17;
  seed ^= seed << 5;
  return seed;
}
const int N = 5e5 + 5;
struct Prime_divisor {
  long long x, tim;
} pri[105];
int k;
long long m, len;
long long d[N];
int n;
map<long long, long long> id, phi;
long long ad[N], mu[N];
int u;
void getall(int x, long long now, int v, long long phy) {
  if (x > k) {
    d[++n] = now;
    id[now] = n;
    phi[now] = phy;
    if (v != 0) {
      ad[++u] = now;
      mu[u] = v;
    }
    return;
  }
  for (int i = 0; i <= pri[x].tim; i++, now *= pri[x].x, phy *= pri[x].x) {
    getall(x + 1, now, v * (i == 0 ? 1 : (i == 1 ? -1 : 0)),
           i == 0 ? phy : phy / pri[x].x * (pri[x].x - 1));
  }
}
long long g[N], f[N];
struct divisors {
  int n;
  long long a[105];
  long long& operator[](int x) { return a[x]; }
} A;
long long multi(long long x, long long y, long long mo) {
  long double d = 1;
  d = d * x * y / mo;
  long long t = d;
  long long ret = x * y - t * mo;
  ret = (ret % mo + mo) % mo;
  return ret;
}
long long quickmi(long long x, long long tim, long long mo) {
  long long ret = 1;
  x %= mo;
  for (; tim; tim /= 2, x = multi(x, x, mo))
    if (tim & 1) ret = multi(ret, x, mo);
  return ret;
}
long long func(long long x, long long n) { return (multi(x, x, n) + 1) % n; }
bool miller_rabin(long long v, long long s, long long mo) {
  if (v == 1 || v == mo - 1) return 1;
  for (int i = 1; i <= s; i++) {
    v = multi(v, v, mo);
    if (v == mo - 1 && i < s) return 1;
    if (v == 1) return 0;
  }
  return v == 1;
}
bool isprime(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 s = 0, x = n - 1;
  for (; x % 2 == 0; x /= 2, s++)
    ;
  for (int i = 1; i <= 5; i++) {
    long long v = getrand() % (n - 1) + 1;
    if (!miller_rabin(quickmi(v, x, n), s, n)) return 0;
  }
  return 1;
}
long long absll(long long x) { return x < 0 ? -x : x; }
long long gcd(long long x, long long y) { return !y ? x : gcd(y, x % y); }
void getdivisors(long long n) {
  if (n == 1) return;
  if (isprime(n)) {
    A[++A.n] = n;
    return;
  }
  long long x_fixed = getrand() % n + 1, circle = 2;
  long long x = x_fixed, ret = 1;
  while (ret == 1) {
    for (long long i = 0; i < circle && ret == 1; i++) {
      x = func(x, n);
      ret = gcd(absll(x - x_fixed), n);
    }
    x_fixed = x;
    circle <<= 1;
  }
  getdivisors(ret);
  getdivisors(n / ret);
}
long long getlen(long long mo, long long x) {
  long long len = phi[mo];
  A.n = 0;
  getdivisors(len);
  for (int i = 1; i <= A.n; i++) {
    if (quickmi(x, len / A[i], mo) == 1) len /= A[i];
  }
  return len;
}
int main() {
  seed = 83727232;
  cin >> m >> len;
  long long x = m;
  for (int i = 2; i <= 1e7; i++)
    if ((x % i) == 0) {
      pri[++k].x = i;
      pri[k].tim = 0;
      while (x % i == 0) {
        x /= i;
        pri[k].tim++;
      }
    }
  if (x > 1) {
    pri[++k].x = x;
    pri[k].tim = 1;
  }
  getall(1, 1, 1, 1);
  for (int i = 1; i <= n; i++) g[i] = m / d[i] - 1;
  for (int i = 1; i <= n; i++) f[i] = g[i];
  for (int v = 1; v <= k; v++)
    for (int i = 1; i <= n; i++)
      if (d[i] % pri[v].x == 0) {
        int x = id[d[i] / pri[v].x];
        f[x] = f[x] - f[i];
      }
  long long ans = 0;
  for (int i = 1; i <= n; i++)
    if (f[i]) {
      ans = ans + f[i] / getlen(m / d[i], len);
    }
  ans++;
  cout << ans << endl;
  return 0;
}