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;
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
long long m, x, ans;
unordered_map<long long, long long> phi;
vector<long long> p;
int B = 1e4;
long long mult(long long a, long long b, long long M) {
  if (!b) return 0;
  return (mult(a, b / B, M) * B % M + a * (b % B)) % M;
}
long long power(long long base, long long to, long long M) {
  long long ret = 1;
  while (to) {
    if (to & 1) ret = mult(ret, base, M);
    to >>= 1;
    base = mult(base, base, M);
  }
  return ret;
}
long long find(long long a) {
  long long ret = 1;
  for (auto i : p)
    if (a % i == 0) {
      long long temp = 1;
      while (a % i == 0) {
        temp *= i;
        a /= i;
      }
      ret *= phi[temp];
    }
  return ret;
}
long long len(long long x, long long m, long long M) {
  long long temp = m;
  for (long long i = 2; i * i <= temp; i++)
    if (temp % i == 0) {
      while (temp % i == 0) temp /= i;
      while (m % i == 0) {
        m /= i;
        if (power(x, m, M) != 1) {
          m *= i;
          break;
        }
      }
    }
  if (temp != 1 && power(x, m / temp, M) == 1) m /= temp;
  return m;
}
long long solve(long long a) {
  long long temp = find(a);
  return temp / len(x, temp, a);
}
int main() {
  scanf("%lld%lld", &m, &x);
  long long temp = m;
  for (long long i = 2; i * i <= temp; i++)
    if (temp % i == 0) {
      p.push_back(i);
      int freq = 0;
      long long a = 1;
      while (temp % i == 0) {
        freq++;
        temp /= i;
        a *= i;
        phi[a] = a / i * (i - 1);
      }
    }
  if (temp != 1) {
    p.push_back(temp);
    phi[temp] = temp - 1;
  }
  for (long long i = 1; i * i <= m; i++)
    if (m % i == 0) {
      ans += solve(i);
      if (m / i != i) ans += solve(m / i);
    }
  printf("%lld\n", ans);
}