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 int C = 100001;
using ll = long long;
const ll Inf = 1000000000000001;
inline ll mul(ll a, ll b, ll M) {
  if (b == 0) return 1;
  ll c = 0;
  while (b > 0) {
    if (b % 2 == 1) c = (c + a) % M;
    b /= 2;
    a = (a + a) % M;
  }
  return c;
}
inline ll pow(ll a, ll b, ll M) {
  if (b == 0) return 1;
  ll c = 1;
  while (b > 0) {
    if (b % 2 == 1) c = mul(c, a, M);
    b /= 2;
    a = mul(a, a, M);
  }
  return c;
}
ll ps[C], assdiv[C], asstot[C];
void find_all_tots(ll d[], ll s[], ll len, ll div[], ll tot[]) {
  ll acttot = 1, num = 1, j = len - 1, ite = 1;
  for (j = 0; j < len; j++) assdiv[j] = asstot[j] = 1, ps[j] = 0;
  j = len - 1;
  div[0] = 1, tot[0] = 1;
  while (1) {
    while (ps[j] == s[j] && j >= 0) {
      num /= assdiv[j];
      acttot /= asstot[j];
      asstot[j] = 1;
      assdiv[j] = 1;
      ps[j] = 0;
      j--;
    }
    if (j < 0) break;
    ps[j]++;
    num *= d[j];
    assdiv[j] *= d[j];
    if (ps[j] == 1) {
      acttot *= (d[j] - 1);
      asstot[j] = d[j] - 1;
    } else {
      acttot *= d[j];
      asstot[j] *= d[j];
    }
    div[ite] = num;
    tot[ite] = acttot;
    ite++;
    j = len - 1;
  }
}
ll find_divs_tables(ll a, ll d[], ll s[]) {
  ll i = 2, j = 0;
  for (i = 2; i * i <= a; i++) {
    if (a % i == 0) d[j] = i, j++;
    for (; a % i == 0; a /= i) s[j - 1]++;
  }
  if (a > 1) d[j] = a, s[j] = 1, j++;
  return j;
}
ll d[C], s[C], tot[C], divs[C], dt[C], st[C], divt[C], pom[C], pwt[C], powa;
int main() {
  ll ln, numofdivs = 1, numofthots = 1, i = 0, j = 0, lnt;
  ll maxt, m, k, res = 0;
  scanf("%lld %lld", &m, &k);
  ln = find_divs_tables(m, d, s);
  for (i = 0; i < ln; i++) numofdivs *= (s[i] + 1);
  find_all_tots(d, s, ln, divs, tot);
  lnt = find_divs_tables(tot[numofdivs - 1], dt, st);
  for (i = 0; i < lnt; i++) numofthots *= (st[i] + 1);
  find_all_tots(dt, st, lnt, divt, pom);
  for (j = 0; j < numofthots; j++) pwt[j] = pow(k, divt[j], m);
  for (i = 1; i < numofdivs; i++) {
    maxt = 1;
    for (j = 0; j < numofthots; j++) {
      if (tot[i] % divt[j] == 0 && tot[i] / divt[j] > maxt &&
          pwt[j] % divs[i] == 1)
        maxt = tot[i] / divt[j];
    }
    res += maxt;
  }
  printf("%lld\n", res + 1);
  return 0;
}