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;
long long gcd(long long a, long long b) {
  if (a % b == 0) {
    return b;
  } else
    return gcd(b, a % b);
}
int T;
vector<long long> primes;
long long a, m;
long long ans;
long long l, r;
long long cnts(long long fac) { return r / fac - (l - 1) / fac; }
void fenjie(long long n) {
  long long sqt = sqrt(n);
  long long fac = 2;
  while (fac <= sqt) {
    if (n % fac == 0) {
      primes.push_back(fac);
      while (n % fac == 0) n /= fac;
    }
    if (fac == 2)
      ++fac;
    else
      fac += 2;
  }
  if (n != 1) {
    primes.push_back(n);
  }
}
void helper(int i, int curr, int tar, long long pro, long long sign) {
  if (curr == tar) {
    ans += (sign * cnts(pro));
    return;
  }
  if (i >= (int)primes.size()) {
    return;
  }
  if ((int)primes.size() - i > tar - curr) {
    helper(i + 1, curr, tar, pro, sign);
  }
  helper(i + 1, curr + 1, tar, pro * primes[i], sign);
}
int main() {
  cin >> T;
  while (T--) {
    primes.clear();
    cin >> a >> m;
    l = a;
    r = a + m - 1;
    long long g = gcd(a, m);
    m /= g;
    l = ceil((double)(l) / g);
    r = floor((double)(r) / g);
    fenjie(m);
    ans = 0;
    long long sign = 1;
    for (int num = 1; num <= primes.size(); ++num) {
      helper(0, 0, num, 1, sign);
      sign = -sign;
    }
    ans = (r - l + 1) - ans;
    cout << ans << endl;
  }
}
