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>
const long long mod = 100000000000031ll;
long long m, x, p[50], ans;
int k[50], c;
long long d(long long& a, long long b, bool t = 0) {
  if (b < 2 || a % b) return 1;
  long long r = b - 1;
  t ? 1 : k[c]++;
  for (a /= b; a % b == 0;) a /= b, t ? r *= b : k[c]++;
  t ? 1 : p[c++] = b;
  return r;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
unsigned long long mul(long long a, long long b, unsigned long long p) {
  unsigned long long c = 0;
  for (; b; b >>= 17) c = (c + a * (b & 131071)) % p, a = (a << 17) % p;
  return c;
}
long long pw(long long a, long long n, long long p) {
  long long b = 1;
  for (; n; n >>= 1) n& 1 ? b = mul(b, a, p) : 1, a = mul(a, a, p);
  return b;
}
void dfs(int i, long long a, long long d, long long w) {
  if (i == c)
    (ans += mul(gcd(m, pw(x, a / d, m) - 1), w, mod)) %= mod;
  else
    for (int j = 0; j <= k[i]; j++)
      dfs(i + 1, a, d, w), d *= p[i], w *= p[i] - !j;
}
int main() {
  scanf("%lld%lld", &m, &x);
  long long a = m, b = d(a, 2, 1) * d(a, 3, 1);
  for (int i = 5; 1ll * i * i <= a; i += 6) b *= d(a, i, 1) * d(a, i + 2, 1);
  b *= d(a, a, 1);
  a = b;
  d(b, 2);
  d(b, 3);
  for (int i = 5; 1ll * i * i <= a; i += 6) d(b, i), d(b, i + 2);
  d(b, b);
  dfs(0, a, 1, 1);
  ans = mul(ans, pw(a, mod - 2, mod), mod);
  printf("%lld\n", ans);
}