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>
std::vector<long long int> prime(long long int upper) {
  std::vector<bool> is_prime(upper + 1, true);
  for (auto i = 2LL; i * i <= upper; ++i) {
    if (is_prime[i])
      for (auto j = i * i; j <= upper; j += i) {
        is_prime[j] = false;
      }
  }
  std::vector<long long int> result;
  for (auto i = 2; i < is_prime.size(); ++i) {
    if (is_prime[i]) result.push_back(i);
  }
  return result;
}
long long int gcd(long long int a, long long int b) {
  return b == 0 ? a : gcd(b, a % b);
}
int main() {
  std::cin.tie(0);
  std::cin.sync_with_stdio(false);
  const auto primes = prime(100000);
  int t;
  std::cin >> t;
  for (auto i = 0; i < t; ++i) {
    long long int a, m;
    std::cin >> a >> m;
    const auto g = gcd(a, m);
    a /= g;
    m /= g;
    const auto max = m;
    long long int phi = m;
    for (auto i = 0; i < primes.size() && primes[i] * primes[i] <= m; ++i) {
      if (m % primes[i] == 0) {
        phi = phi / primes[i] * (primes[i] - 1);
        while (m % primes[i] == 0) {
          m /= primes[i];
        }
      }
    }
    if (m != 1) {
      phi = phi / m * (m - 1);
    }
    std::cout << phi << '\n';
  }
}
