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;
int T;
long long a, m;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
bool isprime(long long x) {
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
long long tot(long long p, long long below) {
  long long h = below;
  for (long long i = 1; i * i <= p; i++) {
    if (p % i != 0) continue;
    if (i != 1 && isprime(i)) h = (h / i) * (i - 1);
    if (p != i && i * i != p && isprime(p / i))
      h = (h / (p / i)) * ((p / i) - 1);
  }
  return h;
}
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%lld", &a, &m);
    long long G = gcd(a, m);
    long long k = m / G;
    long long l = a / G;
    printf("%lld\n", tot(k, l + k) - tot(k, l));
  }
  return 0;
}
