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;
static inline void canhazfast() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}
template <typename T>
T gcd(T a, T b) {
  return b == 0 ? a : gcd(b, a % b);
}
template <typename T>
T extgcd(T a, T b, T &x, T &y) {
  T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
  while (b) {
    T q = a / b;
    a %= b;
    swap(a, b);
    x0 -= q * x1;
    swap(x0, x1);
    y0 -= q * y1;
    swap(y0, y1);
  }
  x = x0;
  y = y0;
  return a;
}
static inline int ctz(unsigned x) { return __builtin_ctz(x); }
static inline int ctzll(unsigned long long x) { return __builtin_ctzll(x); }
static inline int clz(unsigned x) { return __builtin_clz(x); }
static inline int clzll(unsigned long long x) { return __builtin_clzll(x); }
static inline int popcnt(unsigned x) { return __builtin_popcount(x); }
static inline int popcntll(unsigned long long x) {
  return __builtin_popcountll(x);
}
static inline int bsr(unsigned x) { return 31 ^ clz(x); }
static inline int bsrll(unsigned long long x) { return 63 ^ clzll(x); }
unsigned long long mmul(unsigned long long a, unsigned long long b,
                        unsigned long long m) {
  unsigned long long r = 0;
  for (; b; b >>= 1) {
    if (b & 1) {
      r += a;
      if (r >= m) r -= m;
    }
    a += a;
    if (a >= m) a -= m;
  }
  return r;
}
unsigned long long mpow(unsigned long long b, unsigned long long e,
                        unsigned long long m) {
  unsigned long long r = 1;
  for (; e; e >>= 1) {
    if (e & 1) r = mmul(r, b, m);
    b = mmul(b, b, m);
  }
  return r;
}
unsigned long long ipow(unsigned long long b, unsigned long long e) {
  unsigned long long r = 1;
  for (; e; e >>= 1) {
    if (e & 1) r *= b;
    b *= b;
  }
  return r;
}
vector<pair<unsigned long long, int> > factorize(unsigned long long n) {
  vector<pair<unsigned long long, int> > f;
  int e2 = ctzll(n);
  if (e2) f.emplace_back(2, e2);
  n >>= e2;
  int e3 = 0;
  for (;;) {
    unsigned long long q = n / 3, r = n % 3;
    if (r) break;
    n = q;
    ++e3;
  }
  if (e3) f.emplace_back(3, e3);
  for (unsigned long long p = 5, d = 2;; p += d, d ^= 6) {
    unsigned long long q = n / p, r = n % p;
    if (q < p) break;
    int e = 0;
    while (!r) {
      n = q;
      q = n / p;
      r = n % p;
      ++e;
    }
    if (e) f.emplace_back(p, e);
  }
  if (n > 1) f.emplace_back(n, 1);
  return f;
}
unsigned long long m, x, ans;
vector<pair<unsigned long long, unsigned long long> > dmx;
unsigned long long ord(unsigned long long n, unsigned long long phi,
                       unsigned long long x) {
  if (n == 1) return 1;
  for (pair<unsigned long long, unsigned long long> d : dmx) {
    if (phi < d.first) break;
    if (phi % d.first) continue;
    if (d.second % n == 1) return d.first;
  }
  return phi;
}
void dfs(const vector<pair<unsigned long long, int> > &f,
         unsigned long long n = 1, unsigned long long phi = 1, size_t i = 0,
         int j = 0) {
  if (i == f.size()) return void(ans += phi / ord(n, phi, x % n));
  unsigned long long p = f[i].first;
  int e = f[i].second;
  dfs(f, n, phi, i + 1, 0);
  if (j < e) dfs(f, n * p, phi * (j ? p : p - 1), i, j + 1);
}
int main() {
  vector<pair<unsigned long long, int> > f;
  unsigned long long phim = 1;
  vector<pair<unsigned long long, unsigned long long> > tmp;
  scanf("%llu%llu", &m, &x);
  f = factorize(m);
  for (const auto &pf : f)
    phim *= (pf.first - 1) * ipow(pf.first, pf.second - 1);
  for (unsigned long long d = 1;; ++d) {
    unsigned long long q = phim / d, r = phim % d;
    if (q < d) break;
    if (r) continue;
    dmx.emplace_back(d, mpow(x, d, m));
    if (q != d) tmp.emplace_back(q, mpow(x, q, m));
  }
  while (!tmp.empty()) dmx.push_back(tmp.back()), tmp.pop_back();
  dfs(f);
  printf("%llu\n", ans);
  return 0;
}