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 long long MOD = 1e9 + 7;
long long t, a, m, b, ans;
map<long long, long long> mp;
vector<long long> v;
long long gcd(long long x, long long y) {
  if (x % y == 0) return y;
  return gcd(y, x % y);
}
int main() {
  cin >> t;
  for (int tn = 0; tn < t; tn++) {
    cin >> a >> m;
    b = gcd(a, m);
    ans = (a + m - 1) / b - (a - 1) / b;
    long long lb = a / b, ub = (a + m - 1) / b;
    m /= b;
    mp.clear();
    for (long long i = 2; i * i <= m; i++) {
      while (m % i == 0) {
        m /= i;
        mp[i]++;
      }
    }
    if (m > 1) mp[m]++;
    v.clear();
    for (map<long long, long long>::iterator it = mp.begin(); it != mp.end();
         it++)
      v.push_back(it->first);
    long long res = 0;
    for (int i = 1; i <= (1 << v.size()) - 1; i++) {
      long long tmp = 1;
      for (int j = 0; j < v.size(); j++)
        if ((i & (1 << j)) > 0) tmp *= v[j];
      if (__builtin_popcount(i) % 2 == 1)
        res += ub / tmp - (lb - 1) / tmp;
      else
        res -= ub / tmp - (lb - 1) / tmp;
    }
    cout << ans - res << endl;
  }
  return 0;
}
