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 int fastpow(long long int base, long long int exp, long long int M) {
  long long int res = 1;
  while (exp > 0) {
    if (exp & 1) res = (res * base) % M;
    base = (base * base) % M;
    exp >>= 1;
  }
  return res;
}
vector<long long int> par, sz, vis, dis;
vector<vector<long long int>> graph;
vector<vector<pair<long long int, long long int>>> wgraph;
void init(long long int n) {
  par.resize(n);
  sz.resize(n);
  wgraph.resize(n);
  dis.resize(n);
  vis.resize(n);
  graph.resize(n);
  for (long long int i = 0; i <= n - 1; ++i) {
    par[i] = i;
    sz[i] = 1;
    dis[i] = INT_MAX;
  }
}
long long int root(long long int a) {
  while (a != par[a]) {
    par[a] = par[par[a]];
    a = par[a];
  }
  return a;
}
void unio(long long int a, long long int b) {
  long long int r_a = root(a);
  long long int r_b = root(b);
  if (par[r_a] != r_b) {
    if (sz[r_a] < sz[r_b]) {
      par[r_a] = par[r_b];
      sz[r_b] += sz[r_a];
      sz[r_a] = 0;
    } else {
      par[r_b] = par[r_a];
      sz[r_a] += sz[r_b];
      sz[r_b] = 0;
    }
  }
}
long long int gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long int a;
long long int phi(long long int n) {
  long long int ans = n;
  for (long long int p = 2; p * p <= n; ++p) {
    if (n % p == 0) {
      while (n % p == 0) n /= p;
      ans -= ans / p;
    }
  }
  if (n > 1) ans -= ans / n;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t;
  cin >> t;
  while (t--) {
    long long int m;
    cin >> a >> m;
    long long int tp = gcd(a, m);
    if (tp == 1) {
      cout << phi(m) << "\n";
    } else {
      long long int temp = m / tp;
      cout << phi(temp) << "\n";
    }
  }
  return 0;
}
