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 std::cin;
using std::cout;
using std::lower_bound;
using std::max;
using std::min;
using std::random_shuffle;
using std::reverse;
using std::sort;
using std::swap;
using std::unique;
using std::upper_bound;
using std::vector;
void open(const char *s) {}
int rd() {
  int s = 0, c, b = 0;
  while (((c = getchar()) < '0' || c > '9') && c != '-')
    ;
  if (c == '-') {
    c = getchar();
    b = 1;
  }
  do {
    s = s * 10 + c - '0';
  } while ((c = getchar()) >= '0' && c <= '9');
  return b ? -s : s;
}
void put(int x) {
  if (!x) {
    putchar('0');
    return;
  }
  static int c[20];
  int t = 0;
  while (x) {
    c[++t] = x % 10;
    x /= 10;
  }
  while (t) putchar(c[t--] + '0');
}
int upmin(int &a, int b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
int upmax(int &a, int b) {
  if (b > a) {
    a = b;
    return 1;
  }
  return 0;
}
const int N = 100010;
long long c[N];
int cnt1;
long long d[N];
int cnt2;
long long n, x;
long long phi[N];
long long mul(long long a, long long b, long long c) {
  long long temp = (a * b - (long long)((long double)a / c * b + 1.0e-8) * c);
  return temp >= 0 ? (temp >= c ? temp - c : temp) : temp + c;
}
long long fp2(long long a, long long b, long long c) {
  long long s = 1;
  for (; b; b >>= 1, a = mul(a, a, c))
    if (b & 1) s = mul(s, a, c);
  return s;
}
long long fp(long long a, long long b, long long c) {
  long long s = 1;
  for (; b; b >>= 1, a = a * a % c)
    if (b & 1) s = s * a % c;
  return s;
}
vector<std::pair<long long, long long> > e[N];
vector<std::pair<long long, long long> > f1, f2;
int main() {
  open("cf981h");
  cin >> n >> x;
  for (int i = 1; (long long)i * i <= n; i++)
    if (n % i == 0) {
      c[++cnt1] = i;
      if ((long long)i * i != n) c[++cnt1] = n / i;
    }
  long long m = n;
  for (int i = 2; (long long)i * i <= n; i++)
    if (m % i == 0) {
      d[++cnt2] = i;
      while (m % i == 0) m /= i;
    }
  if (m != 1) d[++cnt2] = m;
  for (int i = 1; i <= cnt2; i++) {
    long long y = d[i] - 1;
    for (int j = 2; (long long)j * j <= y; j++)
      if (y % j == 0) {
        int s = 0;
        while (y % j == 0) {
          y /= j;
          s++;
        }
        e[i].push_back(std::pair<long long, long long>(j, s));
      }
    if (y != 1) e[i].push_back(std::pair<long long, long long>(y, 1));
  }
  sort(c + 1, c + cnt1 + 1);
  long long ans = 0;
  for (int i = 2; i <= cnt1; i++) {
    phi[i] = c[i];
    for (int j = 1; j <= cnt2; j++)
      if (c[i] % d[j] == 0) phi[i] = phi[i] / d[j] * (d[j] - 1);
    long long y = x % c[i];
    f1.clear();
    for (int j = 1; j <= cnt2; j++)
      if (c[i] % d[j] == 0) {
        int s = 0;
        long long temp = c[i];
        while (temp % d[j] == 0) {
          temp /= d[j];
          s++;
        }
        for (auto v : e[j]) f1.push_back(v);
        if (s > 1) f1.push_back(std::pair<long long, long long>(d[j], s - 1));
      }
    sort(f1.begin(), f1.end());
    f2.clear();
    for (auto v : f1)
      if (!f2.empty() && f2.back().first == v.first)
        f2.back().second += v.second;
      else
        f2.push_back(v);
    long long s = 1;
    for (auto v : f2) {
      long long s2 =
          fp2(y, phi[i] / fp(v.first, v.second, 0x7fffffffffffffffll), c[i]);
      long long s4 = 1;
      for (int j = 0; j <= v.second; j++) {
        if (s2 == 1) {
          s *= s4;
          break;
        }
        s2 = fp2(s2, v.first, c[i]);
        s4 *= v.first;
      }
    }
    ans += phi[i] / s;
  }
  ans++;
  cout << ans;
  return 0;
}