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.
/**
 * Accomplished using the EduTools plugin by JetBrains https://plugins.jetbrains.com/plugin/10081-edutools
 */

import java.util.*;
import java.io.*;

public class Main {
   private static final int MAX = 100000;

   public static void main(String[] args) throws IOException {

      boolean[] sieve =  new boolean[MAX + 1];
      Arrays.fill(sieve, true);
      int pc = MAX - 1;
      //ignore 0 and 1

      for (int i = 2; i <= MAX; ++i) {
         if (sieve[i]) {
            int composite = i << 1;
            while (composite <= MAX) {
               if (sieve[composite]) {
                  --pc;
                  sieve[composite] = false;
               }
               composite += i;
            }
         }
      }

      int[] primes = new int[pc];
      for (int i = 2, j = 0; j < pc; ++i) {
         if (sieve[i]) {
            primes[j++] = i;
         }
      }

      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

      int T = Integer.parseInt(br.readLine());

      while (T-- > 0) {
         String[] line = br.readLine().split(" ");
         long a = Long.parseLong(line[0]), m = Long.parseLong(line[1]);

         long g = gcd(a, m);
         Map<Long, Integer> factors = new HashMap<>();
         int i = 0;

         m /= g;
         while (m > 1 && i < pc) {
            while (m % primes[i] == 0) {
                  m /= primes[i];
                  factors.put((long)primes[i], factors.getOrDefault((long)primes[i], 0) + 1);
            }
            ++i;
         }
         if (m != 1) {
            factors.put(m, 1);
         }

         long ans = 1;

         for (Map.Entry<Long, Integer> e: factors.entrySet()) {
            ans *= (e.getKey() - 1) * pow(e.getKey(), e.getValue() - 1);
         }

         bw.write(Long.toString(ans));
         bw.newLine();
      }

      br.close();
      bw.close();
   }

   private static long gcd(long a, long b) {
      while (a != 0) {
         long reduced = b % a;
         b = a;
         a = reduced;
      }

      return b;
   }

   private static long pow(long base, int exp) {
      long res = 1;

      while (exp > 0) {
         if ((exp & 1) == 1) {
            res *= base;
         }
         base *= base;
         exp >>= 1;
      }

      return res;
   }
}