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.
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, long long> > v, V[20];
long long m, x, c[20], n, q[100], ans;
long long mul(long long x, long long y, long long mo) {
  long long t = x * y - (long long)((long double)x / mo * y) * mo;
  return (t % mo + mo) % mo;
}
long long power(long long x, long long y, long long mo) {
  long long s = 1;
  for (; y; y /= 2, x = mul(x, x, mo))
    if (y & 1) s = mul(s, x, mo);
  return s;
}
void divide(vector<pair<long long, long long> > &vec, long long m) {
  int tmp = 0;
  for (int i = 2; 1ll * i * i <= m; i++)
    if (m % i == 0) {
      vec.push_back(pair<long long, long long>(i, 0));
      for (; m % i == 0; m /= i, ++vec[tmp].second)
        ;
      ++tmp;
    }
  if (m != 1) vec.push_back(pair<long long, long long>(m, 1));
}
void solve(long long val) {
  if (val == 1) {
    ++ans;
    return;
  }
  long long phi = 1, top = 0, tmp = 1, v = x % val;
  for (int i = (int)(0); i <= (int)(n - 1); i++)
    if (c[i]) {
      phi *= ::v[i].first - 1;
      for (auto j : V[i])
        for (int k = (int)(1); k <= (int)(j.second); k++) q[++top] = j.first;
      for (int j = (int)(2); j <= (int)(c[i]); j++) {
        phi *= ::v[i].first;
        q[++top] = ::v[i].first;
      }
    }
  for (int i = (int)(1); i <= (int)(top); i++)
    if (power(v, phi / q[i], val) == 1) tmp *= q[i], phi /= q[i];
  ans += tmp;
}
void dfs(int x, long long val) {
  if (x == n) return solve(val);
  for (c[x] = 0; c[x] <= v[x].second; ++c[x])
    dfs(x + 1, val), val *= v[x].first;
}
int main() {
  scanf("%lld%lld", &m, &x);
  divide(v, m);
  n = v.size();
  for (int i = (int)(0); i <= (int)(n - 1); i++) divide(V[i], v[i].first - 1);
  dfs(0, 1);
  printf("%lld\n", ans);
}
