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<int> primes;
void sieve(int n) {
  vector<bool> isPrime(n + 1, true);
  for (int i = 2; i <= n; ++i) {
    if (isPrime[i]) primes.push_back(i);
    for (int p : primes) {
      int d = i * p;
      if (d > n) break;
      isPrime[d] = false;
      if (i % p == 0) break;
    }
  }
}
vector<pair<long long int, int> > factorize(long long int n) {
  vector<pair<long long int, int> > f;
  for (long long int p : primes) {
    if (p * p > n) break;
    if (n % p == 0) {
      int pot = 0;
      while (n % p == 0) n /= p, ++pot;
      f.emplace_back(p, pot);
    }
  }
  if (n > 1) f.emplace_back(n, 1);
  return f;
}
long long int multMod(long long int a, long long int b, long long int n) {
  long long int ans = 0;
  a %= n, b %= n;
  if (abs(b) > abs(a)) swap(a, b);
  if (b < 0) {
    a *= -1, b *= -1;
  }
  while (b) {
    if (b & 1) ans = (ans + a) % n;
    b >>= 1;
    a = (a + a) % n;
  }
  return ans;
}
long long int pow(long long int b, long long int e) {
  long long int ans = 1;
  while (e) {
    if (e & 1) ans *= b;
    e >>= 1;
    b *= b;
  }
  return ans;
}
long long int powMod(long long int b, long long int e, long long int m) {
  long long int ans = 1;
  b %= m;
  while (e) {
    if (e & 1) ans = multMod(ans, b, m);
    e >>= 1;
    b = multMod(b, b, m);
  }
  return ans;
}
long long int multiplicativeOrder(long long int x, long long int m,
                                  long long int order) {
  auto f = factorize(order);
  for (auto& factor : f) {
    long long int p = factor.first;
    int a = factor.second;
    order /= pow(p, a);
    long long int tmp = powMod(x, order, m);
    while (tmp != 1) {
      tmp = powMod(tmp, p, m);
      order *= p;
    }
  }
  return order;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long int m, x;
  cin >> m >> x;
  sieve(sqrt(m) + 10);
  auto f = factorize(m);
  long long int ans = 0;
  function<void(vector<pair<long long int, int> >, int, long long int)> dfs =
      [&](vector<pair<long long int, int> > acum, int pos, long long int d) {
        if (pos == f.size()) {
          long long int phi_d = d;
          for (auto& factor : acum) {
            if (factor.second) phi_d -= phi_d / factor.first;
          }
          ans += phi_d / multiplicativeOrder(x, d, phi_d);
          return;
        }
        long long int prod = d;
        for (int i = 0; i <= f[pos].second; ++i) {
          dfs(acum, pos + 1, prod);
          acum[pos].second++;
          prod *= f[pos].first;
        }
      };
  vector<pair<long long int, int> > acum;
  for (auto factor : f) {
    acum.emplace_back(factor.first, 0);
  }
  dfs(acum, 0, 1);
  cout << ans << "\n";
  return 0;
}