You are given two integers a and m. Calculate the number of integers x such that 0 ≤ x < m and \gcd(a, m) = \gcd(a + x, m).

Note: \gcd(a, b) is the greatest common divisor of a and b.

Input

The first line contains the single integer T (1 ≤ T ≤ 50) — the number of test cases.

Next T lines contain test cases — one per line. Each line contains two integers a and m (1 ≤ a < m ≤ 10^{10}).

Output

Print T integers — one per test case. For each test case print the number of appropriate x-s.

Example

Input


3
4 9
5 10
42 9999999967


Output


6
1
9999999966

Note

In the first test case appropriate x-s are [0, 1, 3, 4, 6, 7].

In the second test case the only appropriate x is 0.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
const int mod = 1000000007;
int sushu[maxn], cntOfPrime;
long long product[50][50];
map<int, int>::iterator it;
bool notPrime[maxn];
int factor[50];
int cntFac[50];
long long Left, Right, g;
int cnt1;
int num;
void dfs(long long preProduct, int x) {
  if (x == cnt1) {
    if (preProduct >= Left) {
      cout << preProduct * g << endl;
      num++;
    }
    return;
  }
  for (int i = 0; i <= cntFac[x]; ++i) {
    if (preProduct > Right / product[x][i]) break;
    dfs(preProduct * product[x][i], x + 1);
  }
}
void getPrime() {
  int cnt = 0, n = maxn - 50;
  for (int i = 2; i <= n; ++i) {
    if (!notPrime[i]) sushu[cnt++] = i;
    for (int j = 0; j < cnt && 1ll * i * sushu[j] <= n; ++j) {
      notPrime[i * sushu[j]] = true;
      if (i % sushu[j] == 0) break;
    }
  }
  cntOfPrime = cnt;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
void Fenjie(long long x, map<int, int> &mp) {
  long long ans = x;
  for (int i = 0; sushu[i] <= x / sushu[i]; ++i) {
    int p = sushu[i];
    if (x % p) continue;
    ans = ans / p * (p - 1);
    int c = 0;
    while (x % p == 0) {
      x /= p;
      c++;
    }
    mp[p] = c;
  }
  if (x > 1) mp[x] = 1, ans = ans / x * (x - 1);
  cout << ans << endl;
}
int main() {
  int T;
  long long m, a;
  getPrime();
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%lld", &a, &m);
    g = gcd(a, m);
    long long b = m / g;
    map<int, int> mp;
    Fenjie(b, mp);
    continue;
  }
  return 0;
}
