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;
const int MOD = (int)1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline long long isqrt(long long k) {
  long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
template <class T>
T mulmod(T a, T b, T p) {
  a %= p, b %= p;
  T q = (T)((long double)a * b / p);
  T r = a * b - q * p;
  while (r < 0) r += p;
  while (r >= p) r -= p;
  return r;
}
template <class T>
T powmod(T n, T k, T p) {
  if (!n) return 0;
  T r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = mulmod(r, n, p);
    n = mulmod(n, n, p);
  }
  return r;
}
long long ff(long long x, long long m, long long m1) {
  vector<long long> vals;
  for (long long i = 1; i * i <= m1; i++)
    if (m1 % i == 0) {
      if (powmod(x, i, m) == 1) {
        return i;
      }
      if (i < m1 / i) vals.push_back(m1 / i);
    }
  reverse((vals).begin(), (vals).end());
  for (long long i : vals) {
    if (powmod(x, i, m) == 1) {
      return i;
    }
  }
  assert(0);
  return 0;
}
void chemthan() {
  long long m, x;
  cin >> m >> x;
  long long mm = m;
  map<long long, int> hs, hs2, hs3;
  for (int i = 2; (long long)i * i <= m; i++) {
    while (m % i == 0) hs[i]++, m /= i;
  }
  if (m > 1) hs[m]++;
  m = mm;
  long long m1 = m;
  for (auto it : hs) {
    long long w = 1;
    while (m % it.first == 0) m /= it.first, w *= it.first;
    m *= w;
    if (w > 1) {
      m1 /= it.first;
      m1 *= it.first - 1;
    }
  }
  long long fod = ff(x, m, m1);
  queue<long long> que;
  que.push(m), que.push(fod), hs2[m] = 1;
  for (int i = 2; (long long)i * i <= fod; i++) {
    while (fod % i == 0) fod /= i, hs3[i]++;
  }
  if (fod > 1) hs3[fod]++;
  long long res = 0;
  while (int((que).size())) {
    long long m = que.front();
    que.pop();
    long long od = que.front();
    que.pop();
    long long m1 = m;
    for (auto it : hs) {
      long long w = 1;
      while (m % it.first == 0) m /= it.first, w *= it.first;
      m *= w;
      if (w > 1) {
        m1 /= it.first;
        m1 *= it.first - 1;
      }
      if (m % it.first == 0) {
        long long nm = m / it.first;
        long long nod = od;
        while (1) {
          int found = 0;
          for (auto it : hs3) {
            if (nod % it.first == 0 && powmod(x, nod / it.first, nm) == 1) {
              nod /= it.first;
              found = 1;
            }
          }
          if (!found) break;
        }
        if (!hs2[nm]) {
          hs2[nm] = 1;
          que.push(nm), que.push(nod);
        }
      }
    }
    if (m > 1) {
      res += m1 / od;
    } else {
      res++;
    }
  }
  cout << res << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}