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;
vector<long long> p;
bitset<1000000 + 5> c;
void ciur() {
  int i, j;
  for (i = 2; i * i <= 1000000; i++) {
    if (c[i] == 0)
      for (j = i; j * i <= 1000000; j++) c[j * i] = 1;
  }
  for (i = 2; i <= 1000000; i++)
    if (c[i] == 0) p.push_back(i);
}
long long cmmdc(long long a, long long b) {
  long long r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}
long long t, a, b, x, y;
int main() {
  cin >> t;
  ciur();
  while (t--) {
    cin >> a >> b;
    y = b / cmmdc(a, b);
    long long auxx = y;
    x = a / cmmdc(a, b);
    vector<long long> v;
    long long k = 0, s = 0;
    while (k < p.size() && p[k] * p[k] <= y) {
      if (y % p[k] == 0) {
        v.push_back(p[k]);
        while (y % p[k] == 0) y /= p[k];
      }
      k++;
    }
    if (y != 1) v.push_back(y);
    for (int i = 0; i < (1 << v.size()); i++) {
      long long prod = 1, aux = 0;
      for (int j = 0; j < v.size(); j++)
        if (i & (1 << j)) {
          prod *= v[j];
          aux++;
        }
      if (aux % 2)
        s = s - ((x + auxx - 1) / prod - (x - 1) / prod);
      else
        s = s + ((x + auxx - 1) / prod - (x - 1) / prod);
    }
    cout << s << '\n';
  }
  return 0;
}
