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;
long long int n, x;
long long int mult(long long int a, long long int b, long long int m) {
  if (a == 0 || b == 0) {
    return 0;
  }
  a %= m;
  b %= m;
  if (a == 1) {
    return b;
  }
  if (b == 1) {
    return a;
  }
  long long int a2 = mult(a, b / 2, m);
  if ((b & 1) == 0) {
    return (a2 + a2) % m;
  } else {
    return ((a % m) + (a2 + a2)) % m;
  }
}
long long int pw(long long int a, long long int b, long long int m) {
  if (b == 0) {
    return 1;
  }
  long long int ans = pw(a, b / 2, m);
  ans = mult(ans, ans, m);
  if (b % 2) {
    ans = mult(a, ans, m);
  }
  return ans;
}
vector<int> primes;
bool comp[10000005];
map<long long int, long long int> pws;
long long int ord(long long int a, long long int m, long long int phi,
                  multiset<long long int> &fac) {
  for (long long int pr : fac) {
    while (phi % pr == 0) {
      if (pws[phi / pr] % m == 1) {
        phi /= pr;
      } else {
        break;
      }
    }
  }
  return phi;
}
long long int phi(multiset<long long int> &fac) {
  long long int an = 1;
  long long int prev = -1;
  long long int toadd = 1;
  for (long long int el : fac) {
    if (el == prev) {
      toadd *= el;
    } else {
      an *= toadd;
      toadd = el - 1;
      prev = el;
    }
  }
  an *= toadd;
  return an;
}
long long int solve(long long int div, multiset<long long int> &prim,
                    long long int ph, multiset<long long int> &prim2) {
  return ph / ord(x, div, ph, prim2);
}
long long int soldiv(multiset<long long int> fac, multiset<long long int> toch,
                     long long int num, long long int ph,
                     multiset<long long int> phfac) {
  if (fac.empty()) {
    return solve(num, toch, ph, phfac);
  }
  long long int x = *fac.begin();
  int cn = 0;
  for (long long int el : fac) {
    if (el == x) {
      cn++;
    } else {
      break;
    }
  }
  fac.erase(x);
  long long int an = 0;
  for (int times = 0; times <= cn; times++) {
    if (times) {
      toch.insert(x);
      num *= x;
      if (times == 1) {
        ph *= x - 1;
        long long int cur = x - 1;
        for (long long int pr : primes) {
          if (pr * pr > cur) {
            break;
          }
          while (cur % pr == 0) {
            cur /= pr;
            phfac.insert(pr);
          }
        }
        if (cur > 1) {
          phfac.insert(cur);
        }
      } else {
        ph *= x;
        phfac.insert(x);
      }
    }
    an += soldiv(fac, toch, num, ph, phfac);
  }
  return an;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  for (int i = 2; i <= 10000000; i++) {
    if (!comp[i]) {
      primes.push_back(i);
      for (long long int j = i; j * i <= 10000000; j++) {
        comp[j * i] = true;
      }
    }
  }
  cin >> n >> x;
  multiset<long long int> prim;
  long long int t = n;
  for (long long int i : primes) {
    if (i * i > t) {
      break;
    }
    while (t % i == 0) {
      t /= i;
      prim.insert(i);
    }
  }
  if (t > 1) {
    prim.insert(t);
  }
  long long int nph = phi(prim);
  for (long long int i = 1; i * i <= nph; i++) {
    if (nph % i == 0) {
      pws[i] = pw(x, i, n);
      pws[nph / i] = pw(x, nph / i, n);
    }
  }
  multiset<long long int> st;
  multiset<long long int> st2;
  cout << soldiv(prim, st, 1, 1, st2) << endl;
  return 0;
}