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;
long long m, x;
vector<long long> factors_m, factors_other;
vector<long long> find_divs(long long num) {
  vector<long long> ret = {};
  for (long long i = 2; i * i <= num; i++)
    if (num % i == 0) {
      ret.push_back(i);
      while (num % i == 0) num = num / i;
    }
  if (num != 1) ret.push_back(num);
  return ret;
}
vector<long long> compress(vector<long long> all) {
  sort(all.begin(), all.end());
  vector<long long> ret = {};
  for (auto k : all)
    if (ret.size() == 0 || ret[ret.size() - 1] != k) ret.push_back(k);
  return ret;
}
long long phi(long long num, vector<long long> divs) {
  long long ret = num;
  for (auto k : divs)
    if (num % k == 0) {
      ret = ret / k * (k - 1);
      while (num % k == 0) num = num / k;
    }
  assert(num == 1);
  return ret;
}
vector<long long> calculate_other() {
  vector<long long> all = find_divs(phi(m, factors_m));
  for (auto k : factors_m) all.push_back(k);
  return compress(all);
}
long long slow_mult(long long x, long long y, long long modulo) {
  int C = 10000;
  long long ret = 0;
  while (y) {
    ret = (ret + x * (y % C)) % modulo;
    y = y / C;
    x = x * C % modulo;
  }
  return ret;
}
long long my_pow(long long a, long long b, long long modulo) {
  if (b == 0) return 1;
  long long mem = my_pow(a, b / 2, modulo);
  long long ret = slow_mult(mem, mem, modulo);
  if (b % 2 == 1) ret = slow_mult(ret, a, modulo);
  return ret;
}
long long ask(long long current_gcd) {
  if (current_gcd == m) return 0;
  long long modulo = m / current_gcd;
  long long cycle = phi(modulo, factors_other);
  long long ret = cycle;
  for (auto k : factors_other)
    if (ret % k == 0) {
      while (ret % k == 0 && my_pow(x, ret / k, modulo) == 1) ret = ret / k;
    }
  return cycle / ret;
}
int main() {
  scanf("%lld%lld", &m, &x);
  factors_m = find_divs(m);
  factors_other = calculate_other();
  long long ret = 1;
  for (long long d = 1; d * d <= m; d++)
    if (m % d == 0) {
      ret = ret + ask(d);
      if (d != m / d && d != 1) ret = ret + ask(m / d);
    }
  printf("%lld\n", ret);
  return 0;
}
