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 long long MOD = 1e9 + 7;
template <typename F>
class Matrix {
  int rowNum, colNum;
  vector<vector<F>> cell;

 public:
  Matrix(int n) : rowNum(n), colNum(n) {
    cell = vector<vector<F>>(n, vector<F>(n, 0));
    for (int i = 0; i < n; i++) cell[i][i] = (F)1;
  }
  Matrix(int n, int m, int fill = 0) : rowNum(n), colNum(m) {
    cell.assign(n, vector<F>(m, fill));
  }
  Matrix(const Matrix &mat) : rowNum(mat.rowNum), colNum(mat.colNum) {
    cell = mat.cell;
  }
  vector<F> &operator[](int i) { return cell[i]; }
  const vector<F> &operator[](int i) const { return cell[i]; }
  Matrix &operator=(const Matrix &mat) {
    rowNum = mat.rowNum;
    colNum = mat.colNum;
    cell = mat.cell;
    return *this;
  }
  Matrix &operator*=(const Matrix &mat) {
    assert(colNum == mat.rowNum);
    Matrix res(rowNum, mat.colNum);
    for (int i = 0; i < rowNum; i++) {
      for (int j = 0; j < mat.colNum; j++) {
        for (int k = 0; k < colNum; k++) {
          (res[i][j] += cell[i][k] * mat[k][j]) %= 998244352;
        }
      }
    }
    return *this = res;
  }
  Matrix &operator^=(long long p) {
    assert(rowNum == colNum && p >= 0);
    Matrix res(rowNum);
    for (; p; p >>= 1) {
      if (p & 1) res *= *this;
      *this *= *this;
    }
    return *this = res;
  }
  friend istream &operator>>(istream &is, Matrix &mat) {
    for (int i = 0; i < mat.rowNum; i++)
      for (int j = 0; j < mat.colNum; j++) is >> mat[i][j];
    return is;
  }
  friend ostream &operator<<(ostream &os, const Matrix &mat) {
    for (int i = 0; i < mat.rowNum; i++)
      for (int j = 0; j < mat.colNum; j++)
        os << mat[i][j] << " \n"[j == mat.colNum - 1];
    return os;
  }
  Matrix operator*(const Matrix &b) {
    Matrix res(*this);
    return (res *= b);
  }
  Matrix operator^(const long long p) {
    Matrix res(*this);
    return (res ^= p);
  }
};
long long __gcd(long long a, long long b) {
  if (not a or not b)
    return a | b;
  else
    return __gcd(b, a % b);
}
template <typename F>
tuple<F, F, F> ext_gcd(F a, F b) {
  if (!a or !b) return {a != 0, b != 0, a | b};
  F x, y, g;
  tie(x, y, g) = ext_gcd(b, a % b);
  return {y, x - a / b * y, g};
}
template <typename F>
F powM(F x, F p, F mod) {
  F s = 1, m = x % mod;
  for (; p; m = m * m % mod, p >>= 1)
    if (p & 1) s = s * m % mod;
  return s;
}
template <typename F>
F dangerous_mul(F a, F b, F mod) {
  return (a * b - (long long)((long double)a * b / mod) * mod) % mod;
}
template <typename F>
vector<F> linear_inv(F p, int k) {
  vector<F> inv(min(p, F(1 + k)));
  inv[1] = 1;
  for (int i = 2; i < inv.size(); ++i) inv[i] = (p - p / i) * inv[p % i] % p;
  return inv;
}
namespace LLFactorization {
long long LLmul(long long x, long long y, long long mod) {
  long long m = x, s = 0;
  for (; y; y >>= 1, m <<= 1, m = m >= mod ? m - mod : m)
    if (y & 1) s += m, s = s >= mod ? s - mod : s;
  return s;
}
long long powM(long long x, long long p, long long mod) {
  long long s = 1, m = x % mod;
  for (; p; m = LLmul(m, m, mod), p >>= 1)
    if (p & 1) s = LLmul(s, m, mod);
  return s;
}
bool miller_rabin(long long n, int s = 7) {
  const long long wits[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
  auto witness = [&](long long a, long long n, long long u, int t) {
    long long x = powM(a, u, n), nx;
    for (int i = 0; i < t; ++i, x = nx) {
      nx = LLmul(x, x, n);
      if (nx == 1 and x != 1 and x != n - 1) return true;
    }
    return x != 1;
  };
  if (n < 2) return 0;
  if (n & 1 ^ 1) return n == 2;
  long long u = n - 1, t = 0, a;
  while (u & 1 ^ 1) u >>= 1, ++t;
  while (s--)
    if ((a = wits[s] % n) and witness(a, n, u, t)) return 0;
  return 1;
}
long long pollard_rho(long long n) {
  auto f = [=](long long x, long long n) { return LLmul(x, x, n) + 1; };
  if (n & 1 ^ 1) return 2;
  while (true) {
    long long x = rand() % (n - 1) + 1, y = 2, d = 1;
    for (int sz = 2; d == 1; y = x, sz <<= 1)
      for (int i = 0; i < sz and d <= 1; ++i)
        x = f(x, n), d = __gcd(abs(x - y), n);
    if (d and n - d) return d;
  }
}
template <typename F>
vector<pair<F, int>> factor(F m) {
  vector<pair<F, int>> ans;
  while (m > 2e14) {
    F cur = m;
    while (not miller_rabin(cur)) cur = pollard_rho(cur);
    ans.emplace_back(cur, 0);
    while (m % cur == 0) ++ans.back().second, m /= cur;
  }
  for (long long p = 2; p * p <= m; ++p) {
    if (m % p == 0) {
      ans.emplace_back(p, 0);
      while (m % p == 0) ++ans.back().second, m /= p;
    }
  }
  if (m > 1) ans.emplace_back(m, 1);
  sort(ans.begin(), ans.end());
  return ans;
}
}  // namespace LLFactorization
template <typename F>
F phi(F m) {
  auto fac = LLFactorization::factor(m);
  return accumulate(fac.begin(), fac.end(), m, [](F a, pair<F, int> p_r) {
    return a / p_r.first * (p_r.first - 1);
  });
}
template <typename F>
F order(F x, F m) {
  F ans = phi(m);
  for (auto P : LLFactorization::factor(ans)) {
    F p = P.first, t = P.second;
    for (int i = 0; i < t; ++i) {
      if (LLFactorization::powM(x, ans / p, m) == 1)
        ans /= p;
      else
        break;
    }
  }
  return ans;
}
template <typename F>
F cycles(F a, F m) {
  if (m == 1) return 1;
  return phi(m) / order(a, m);
}
template <typename F>
F generator(F p) {
  assert(LLFactorization::miller_rabin(p));
  for (F a = 2; a <= p; ++a)
    if (order(a, p) == p - 1) return a;
}
template <typename F>
F discrete_log(F b, F n, F M) {
  const F NONEXIST = -1;
  map<F, F> att;
  F m = sqrt((double)M) + 1, B = powM(b, m * (M - 2), M);
  for (F cur = 1, i = 0; i < m; ++i, cur = cur * b % M)
    if (not att.count(cur)) att[cur] = i;
  for (F cur = 1, i = 0; i * m < M - 1; ++i, cur = cur * B % M)
    if (att.count(n * cur % M)) return (att[cur * n % M] + i * m) % (M - 1);
  return NONEXIST;
}
template <typename F>
F discrete_kth_root(F k, F m, F p) {
  F g = generator(p);
  F q = discrete_log(g, m, p);
  if (q == -1) return -1;
  F x, y, d;
  tie(x, y, d) = ext_gcd(k, p - 1);
  if (q % d) return -1;
  F w = x;
  if (w < 0) w = w % ((p - 1) / d) + (p - 1) / d;
  F r = 1;
  for (F i = q / d * w; i; i >>= 1) {
    if (i & 1) r = r * g % p;
    g = g * g % p;
  }
  return r;
}
class Solution {
  long long m, x;

 public:
  void run() {
    cin >> m >> x;
    long long ans = 0;
    for (long long i = 1; i * i <= m; ++i) {
      if (m % i == 0) {
        ans += cycles(x % (m / i), m / i);
        if (i * i != m) ans += cycles(x % i, i);
      }
    }
    cout << ans << '\n';
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  Solution().run();
}