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>
namespace Factor {
const int N = 1010000;
int64_t C, fac[10010], n, mut, a[1001000];
int T, cnt, i, l, prime[N], p[N], psize, _cnt;
int64_t _e[100], _pr[100];
std::vector<int64_t> d;
inline int64_t mul(int64_t a, int64_t b, int64_t p) {
  if (p <= 1000000000)
    return a * b % p;
  else if (p <= 1000000000000ll)
    return (((a * (b >> 20) % p) << 20) + (a * (b & ((1 << 20) - 1)))) % p;
  else {
    return (int64_t)((__int128_t)a * b % p);
  }
}
void prime_table() {
  int i, j, tot, t1;
  for (i = 1; i <= psize; i++) p[i] = i;
  for (i = 2, tot = 0; i <= psize; i++) {
    if (p[i] == i) prime[++tot] = i;
    for (j = 1; j <= tot && (t1 = prime[j] * i) <= psize; j++) {
      p[t1] = prime[j];
      if (i % prime[j] == 0) break;
    }
  }
}
void init(int ps) {
  psize = ps;
  prime_table();
}
int64_t powl(int64_t a, int64_t n, int64_t p) {
  int64_t ans = 1;
  for (; n; n >>= 1) {
    if (n & 1) ans = mul(ans, a, p);
    a = mul(a, a, p);
  }
  return ans;
}
bool witness(int64_t a, int64_t n) {
  int t = 0;
  int64_t u = n - 1;
  for (; ~u & 1; u >>= 1) t++;
  int64_t x = powl(a, u, n), _x = 0;
  for (; t; t--) {
    _x = mul(x, x, n);
    if (_x == 1 && x != 1 && x != n - 1) return 1;
    x = _x;
  }
  return _x != 1;
}
bool miller(int64_t n) {
  if (n < 2) return 0;
  if (n <= psize) return p[n] == n;
  if (~n & 1) return 0;
  for (int j = 0; j <= 7; j++)
    if (witness(rand() % (n - 1) + 1, n)) return 0;
  return 1;
}
int64_t gcd(int64_t a, int64_t b) {
  int64_t ret = 1;
  while (a != 0) {
    if ((~a & 1) && (~b & 1))
      ret <<= 1, a >>= 1, b >>= 1;
    else if (~a & 1)
      a >>= 1;
    else if (~b & 1)
      b >>= 1;
    else {
      if (a < b) std::swap(a, b);
      a -= b;
    }
  }
  return ret * b;
}
int64_t rho(int64_t n) {
  for (;;) {
    int64_t X = rand() % n, Y, Z, T = 1, *lY = a, *lX = lY;
    int tmp = 20;
    C = rand() % 10 + 3;
    X = mul(X, X, n) + C;
    *(lY++) = X;
    lX++;
    Y = mul(X, X, n) + C;
    *(lY++) = Y;
    for (; X != Y;) {
      int64_t t = X - Y + n;
      Z = mul(T, t, n);
      if (Z == 0) return gcd(T, n);
      tmp--;
      if (tmp == 0) {
        tmp = 20;
        Z = gcd(Z, n);
        if (Z != 1 && Z != n) return Z;
      }
      T = Z;
      Y = *(lY++) = mul(Y, Y, n) + C;
      Y = *(lY++) = mul(Y, Y, n) + C;
      X = *(lX++);
    }
  }
}
void _factor(int64_t n) {
  for (int i = 0; i < cnt; i++) {
    if (n % fac[i] == 0) n /= fac[i], fac[cnt++] = fac[i];
  }
  if (n <= psize) {
    for (; n != 1; n /= p[n]) fac[cnt++] = p[n];
    return;
  }
  if (miller(n))
    fac[cnt++] = n;
  else {
    int64_t x = rho(n);
    _factor(x);
    _factor(n / x);
  }
}
void dfs(int64_t x, int dep) {
  if (dep == _cnt)
    d.push_back(x);
  else {
    dfs(x, dep + 1);
    for (int i = 1; i <= _e[dep]; i++) dfs(x *= _pr[dep], dep + 1);
  }
}
void norm() {
  std::sort(fac, fac + cnt);
  _cnt = 0;
  for (int i = 0; i < cnt; ++i)
    if (i == 0 || fac[i] != fac[i - 1])
      _pr[_cnt] = fac[i], _e[_cnt++] = 1;
    else
      _e[_cnt - 1]++;
}
std::vector<int64_t> getd() {
  d.clear();
  dfs(1, 0);
  return d;
}
std::vector<int64_t> factor(int64_t n) {
  cnt = 0;
  _factor(n);
  norm();
  return getd();
}
std::vector<std::pair<int64_t, int64_t>> factorG(int64_t n) {
  cnt = 0;
  _factor(n);
  norm();
  std::vector<std::pair<int64_t, int64_t>> d;
  for (int i = 0; i < _cnt; ++i) d.emplace_back(_pr[i], _e[i]);
  return d;
}
bool is_primitive(int64_t a, int64_t p) {
  assert(miller(p));
  std::vector<std::pair<int64_t, int64_t>> D = factorG(p - 1);
  for (int i = 0; i < D.size(); ++i)
    if (powl(a, (p - 1) / D[i].first, p) == 1) return 0;
  return 1;
}
}  // namespace Factor
int64_t powll(int64_t a, int64_t n) {
  int64_t ans = 1;
  for (; n; n >>= 1) {
    if (n & 1) ans = ans * a;
    a = a * a;
  }
  return ans;
}
int64_t mul(int64_t x, int64_t y, int64_t m) {
  x %= m;
  y %= m;
  assert(x >= 0 && y >= 0);
  int64_t d = ((long double)x * y / m);
  d = x * y - d * m;
  if (d >= m) d -= m;
  if (d < 0) d += m;
  return d;
}
int64_t Inv(int64_t q, int64_t m) {
  if (q == 0) return 0;
  assert(q >= 0);
  int64_t a1 = m, b1 = 0, a2 = q, b2 = 1, a3, b3, t;
  while (a2 != 1) {
    t = a1 / a2, a3 = a1 - t * a2, b3 = b1 - mul(t, b2, m), a1 = a2, a2 = a3,
    b1 = b2, b2 = b3;
    if (b2 < 0) b2 += m;
  }
  return b2;
}
int main() {
  Factor::init(500000);
  int64_t m, x;
  std::cin >> m >> x;
  auto factors = Factor::factor(m);
  int64_t ans = 0;
  for (int64_t n : factors) {
    int64_t a = x % n;
    auto for_phi = Factor::factorG(n);
    int64_t phi = n;
    for (auto pr : for_phi) {
      phi -= phi / pr.first;
    }
    auto pfac = Factor::factorG(phi);
    int64_t t = phi;
    for (auto& i : pfac) {
      t /= powll(i.first, i.second);
      int64_t a1 = Factor::powl(a, t, n);
      while (a1 != 1) {
        a1 = Factor::powl(a1, i.first, n);
        t = mul(t, i.first, n);
      }
    }
    ans += phi / t;
  }
  std::cout << ans << '\n';
}