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;
vector<long long> d;
long long mult(long long a, long long b, long long md) {
  a = a % md;
  long long ret = 0;
  while (b) {
    if (b & 1) {
      ret += a;
      if (ret >= md) ret -= md;
    }
    a += a;
    if (a >= md) a -= md;
    b = (b >> 1);
  }
  return ret;
}
long long gcd(long long a, long long b) { return a ? gcd(b % a, a) : b; }
long long qpow(long long x, long long k, long long md) {
  long long ret = 1;
  while (k) {
    if (k & 1) {
      ret = mult(ret, x, md);
    }
    x = mult(x, x, md);
    k = (k >> 1);
  }
  return ret;
}
bool witness(long long a, long long n) {
  long long m = n - 1;
  int j = 0;
  while (!(m & 1)) {
    j++;
    m = (m >> 1);
  }
  long long x = qpow(a, m, n);
  if (x == 1 || x == n - 1) return false;
  while (--j) {
    x = mult(x, x, n);
    if (x == n - 1) return false;
  }
  return true;
}
bool miller_rabin(long long n, int T = 10) {
  if (n < 2) return false;
  if (n == 2) return true;
  if (!(n & 1)) return false;
  while (T--) {
    long long a = rand() % (n - 1) + 1;
    if (witness(a, n)) return false;
  }
  return true;
}
long long c;
long long func(long long x, long long n) { return (mult(x, x, n) + c) % n; }
long long pollard_rho(long long n) {
  long long a = rand() % (n - 1) + 1;
  long long b = a;
  long long d = 1;
  while (d == 1) {
    a = func(a, n);
    b = func(func(b, n), n);
    d = gcd(abs(a - b), n);
  }
  if (d == n) return -1;
  return d;
}
void combine_fac(set<pair<long long, int>>& x, set<pair<long long, int>>& y) {
  set<pair<long long, int>>::iterator it1 = x.begin(), it2 = y.begin(), tp;
  while (it1 != x.end() && it2 != y.end()) {
    if (it1->first < it2->first)
      it1++;
    else if (it1->first > it2->first) {
      tp = it2++;
      x.insert(*tp);
    } else {
      pair<long long, int> add =
          pair<long long, int>(it1->first, it1->second + it2->second);
      tp = it1++;
      x.erase(tp);
      x.insert(add);
      it2++;
    }
  }
  while (it2 != y.end()) {
    tp = it2++;
    x.insert(*tp);
  }
}
set<pair<long long, int>> factorize(long long n) {
  set<pair<long long, int>> divs;
  divs.clear();
  int cnt = 0;
  while (!(n & 1)) {
    cnt++;
    n = (n >> 1);
  }
  if (cnt) divs.insert(pair<long long, int>(2, cnt));
  while (n > 1) {
    if (miller_rabin(n)) {
      set<pair<long long, int>> tmp;
      tmp.clear();
      tmp.insert(pair<long long, int>(n, 1));
      combine_fac(divs, tmp);
      return divs;
    }
    long long d = -1;
    c = 100;
    while (d < 0) {
      d = pollard_rho(n);
      c--;
    }
    while (n % d == 0) {
      set<pair<long long, int>> tmp = factorize(d);
      combine_fac(divs, tmp);
      n /= d;
    }
  }
  return divs;
}
pair<long long, set<pair<long long, int>>> phi(long long n) {
  set<pair<long long, int>> tmp = factorize(n), ret;
  ret.clear();
  vector<set<pair<long long, int>>> q;
  q.clear();
  long long p = n;
  for (auto& v : tmp) {
    q.push_back(factorize(v.first - 1));
    p -= p / v.first;
    if (v.second > 1) ret.insert(pair<long long, int>(v.first, v.second - 1));
  }
  for (auto& v : q) {
    combine_fac(ret, v);
  }
  return make_pair(p, ret);
}
long long m, x;
int main() {
  srand(time(NULL));
  scanf("%lld%lld", &m, &x);
  d.clear();
  for (long long i = 1; i * i <= m; i++) {
    if (m % i == 0) {
      d.push_back(i);
    }
  }
  for (int i = d.size() - 1; i >= 0; i--) {
    if (m / d[i] != d[i]) d.push_back(m / d[i]);
  }
  long long ans = 0;
  for (auto v : d) {
    auto now = phi(v);
    long long pv = now.first;
    set<pair<long long, int>> pf = now.second;
    long long ord = pv;
    for (auto u : pf) {
      for (int i = 1; i <= u.second; i++) ord /= u.first;
      long long cp = qpow(x, ord, v);
      while (cp != 1) {
        ord *= u.first;
        cp = qpow(cp, u.first, v);
      }
    }
    ans += pv / ord;
  }
  printf("%lld\n", ans);
  return 0;
}