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<pair<long long, int>> prime_factorize(long long x) {
  vector<pair<long long, int>> factors;
  for (long long i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      int exp = 0;
      while (x % i == 0) {
        x /= i;
        exp++;
      }
      factors.push_back({i, exp});
    }
  }
  if (x > 1) {
    factors.push_back({x, 1});
  }
  return factors;
}
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long get_count(long long big, long long g,
                    const vector<long long> &limiting_factors) {
  big /= g;
  long long delta = 0;
  int nf = limiting_factors.size();
  for (int i = 0; i < (1 << nf); ++i) {
    long long prod = 1;
    int nb = 0;
    for (int j = 0; j < nf; ++j) {
      if ((1 << j) & i) {
        nb++;
        prod *= limiting_factors[j];
      }
    }
    if (nb % 2 == 1) {
      delta -= big / prod;
    } else {
      delta += big / prod;
    }
  }
  return delta;
}
void solve_case() {
  long long A, M;
  cin >> A >> M;
  long long g = gcd(A, M);
  vector<pair<long long, int>> factors = prime_factorize(M);
  vector<long long> limiting_factors;
  for (pair<long long, int> factor : factors) {
    long long base = factor.first;
    int exp = factor.second;
    int g_exp = 0;
    long long g_ = g;
    while (g_ % base == 0) {
      g_ /= base;
      g_exp++;
    }
    if (g_exp < exp) {
      limiting_factors.push_back(base);
    }
  }
  long long answer = get_count(A + M - 1, g, limiting_factors) -
                     get_count(A - 1, g, limiting_factors);
  cout << answer << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int T;
  cin >> T;
  for (int t = 0; t < T; ++t) {
    solve_case();
  }
  return 0;
}
