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 long long mul(unsigned long long a, unsigned long long b,
                       unsigned long long p) {
  long long res =
      a * b - p * (unsigned long long)((long double)a * (long double)b /
                                       (long double)p);
  return res + p * (res < 0) - p * (res >= (long long)p);
}
long long qpm(long long a, long long b, long long p) {
  long long r = 1;
  do
    if (b & 1) r = mul(r, a, p);
  while (a = mul(a, a, p), b >>= 1);
  return r;
}
const int N = 10000000;
bool ip[N];
vector<int> ps;
void sieve() {
  memset(ip, 1, sizeof(ip));
  ip[1] = 0;
  for (int i = 2; i != N; ++i) {
    if (ip[i]) ps.push_back(i);
    for (int j : ps) {
      if (i * j >= N) break;
      ip[i * j] = 0;
      if (i % j == 0) break;
    }
  }
}
struct pf {
  long long p, c, q;
};
vector<pf> pfd(long long x) {
  vector<pf> res;
  for (long long p : ps) {
    if (p * p > x) break;
    if (x % p) continue;
    res.push_back({p, 0, 1});
    do res.back().c++, res.back().q *= p;
    while ((x /= p) % p == 0);
  }
  if (x != 1) res.push_back({x, 1, x});
  return res;
}
long long phi(long long x) {
  long long r = x;
  for (long long p : ps) {
    if (p * p > x) break;
    if (x % p) continue;
    (r /= p) *= p - 1;
    while (x % p == 0) x /= p;
  }
  if (x != 1) (r /= x) *= x - 1;
  return r;
}
long long ord(long long n, long long phn, const vector<pf>& pfs, long long g) {
  long long res = 1;
  for (pf p : pfs)
    for (long long t = qpm(g, phn / p.q, n); t != 1; res *= p.p)
      t = qpm(t, p.p, n);
  return res;
}
vector<pf> merge(const vector<pf>& p1, const vector<pf>& p2) {
  vector<pf> res;
  int n1 = p1.size(), n2 = p2.size(), i1 = 0, i2 = 0;
  while (i1 != n1 && i2 != n2) {
    if (p1[i1].p < p2[i2].p) {
      res.push_back(p1[i1]);
      i1++;
    } else if (p2[i2].p < p1[i1].p) {
      res.push_back(p2[i2]);
      i2++;
    } else {
      res.push_back({p1[i1].p, p1[i1].c + p2[i2].c, p1[i1].q * p2[i2].q});
      i1++;
      i2++;
    }
  }
  while (i1 != n1) res.push_back(p1[i1++]);
  while (i2 != n2) res.push_back(p2[i2++]);
  return res;
}
long long prod(const vector<pf>& pfs) {
  long long r = 1;
  for (pf p : pfs) r *= p.q;
  return r;
}
void dfs(long long& res, long long g, long long n, const vector<pf>& nf,
         const vector<vector<pf>>& wf, int i, long long m, long long phm,
         vector<pf>& mf) {
  if (i == nf.size()) {
    if (m == 1) return;
    vector<pf> u = mf, v, w;
    for (int i = 0; i != nf.size(); ++i) {
      if (!mf[i].c) continue;
      u[i].c--;
      u[i].q /= u[i].p;
      v = merge(v, wf[i]);
    }
    w = merge(u, v);
    long long t = ord(m, phm, w, g % m);
    assert(phm % t == 0);
    res += phm / t;
  } else {
    dfs(res, g, n, nf, wf, i + 1, m, phm, mf);
    for (int j = 1; j <= nf[i].c; ++j) {
      m /= mf[i].p;
      mf[i].q /= mf[i].p;
      mf[i].c--;
      phm /= mf[i].p - (j == nf[i].c);
      dfs(res, g, n, nf, wf, i + 1, m, phm, mf);
    }
    mf[i] = nf[i];
  }
}
int main(void) {
  sieve();
  long long n, g;
  scanf("%lld%lld", &n, &g);
  long long res = 1;
  vector<pf> nf = pfd(n), mf = nf;
  vector<vector<pf>> wf;
  for (pf p : nf) wf.push_back(p.p == 2 ? vector<pf>(0) : pfd(p.p - 1));
  long long phn = 1;
  for (pf p : nf) phn *= (p.q / p.p) * (p.p - 1);
  dfs(res, g, n, nf, wf, 0, n, phn, mf);
  printf("%lld\n", res);
  return 0;
}