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 x, global;
int counter[100 + 5];
struct number {
  vector<long long int> P, A;
  number() {}
  number(long long int m) {
    int s = sqrtl(m);
    for (int i = 2; i <= s; i++)
      if (m % i == 0) {
        P.push_back(i);
        A.push_back(0);
        while (m % i == 0) {
          m = m / i;
          A.back()++;
        }
        s = sqrtl(m);
      }
    if (m != 1) {
      P.push_back(m);
      A.push_back(1);
    }
  }
  void merge(number ano) {
    int i, j;
    for (i = 0; i < (int)ano.P.size(); i++) {
      for (j = 0; j < (int)P.size(); j++)
        if (P[j] == ano.P[i]) {
          A[j] += ano.A[i];
          break;
        }
      if (j == (int)P.size()) {
        P.push_back(ano.P[i]);
        A.push_back(ano.A[i]);
      }
    }
  }
  long long int eval() {
    long long int ret = 1;
    for (int i = 0; i < (int)P.size(); i++) {
      for (int j = 1; j <= A[i]; j++) ret = ret * P[i];
    }
    return ret;
  }
} M, arr[100 + 5];
long long int mod;
inline long long int eval(long long int value) {
  if (value >= mod) return value - mod;
  return value;
}
inline long long int mul(long long int u, long long int v) {
  if (!v) return 0;
  if (v & 1) return eval((u + mul(u, v - 1)));
  long long int ret = mul(u, v / 2);
  return eval((ret + ret));
}
inline long long int ip(long long int a, long long int p) {
  if (!p) return 1 % mod;
  if (p & 1) return mul(a, ip(a, p - 1));
  long long int ret = ip(a, p / 2);
  return mul(ret, ret);
}
void G(number &d, number &phi) {
  long long int dvxr = d.eval();
  long long int phival = phi.eval();
  long long int ret = phival;
  mod = dvxr;
  long long int nx = x % dvxr;
  long long int nr = 1 % dvxr;
  for (int i = (int)phi.P.size() - 1; i >= 0; i--) {
    while (true) {
      if (phi.A[i] && ip(nx, ret / phi.P[i]) == nr)
        ret /= phi.P[i], phi.A[i]--;
      else
        break;
    }
  }
  global += phival / ret;
}
void F() {
  int i, j;
  number phi, d, ano;
  for (i = 0; i < (int)M.P.size(); i++)
    if (counter[i]) {
      d.P.push_back(M.P[i]);
      d.A.push_back(counter[i]);
    }
  phi = d;
  assert(d.A.size() == d.P.size());
  for (i = 0; i < (int)phi.P.size(); i++) {
    phi.A[i]--;
    for (j = 0; j < (int)M.P.size(); j++)
      if (M.P[j] == phi.P[i]) {
        ano.merge(arr[j]);
        break;
      }
  }
  phi.merge(ano);
  return G(d, phi);
}
void backTrack(int pos) {
  if (pos == (int)M.P.size()) return F();
  for (int c = 0; c <= M.A[pos]; c++) {
    counter[pos] = c;
    backTrack(pos + 1);
  }
}
int main() {
  int i;
  long long int v;
  cin >> v >> x;
  M = number(v);
  for (i = 0; i < (int)M.P.size(); i++) arr[i] = number(M.P[i] - 1);
  backTrack(0);
  cout << global << endl;
  return 0;
}