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.
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1295D
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int T = Integer.parseInt(st.nextToken());
         while(T-- > 0)
         {
            st = new StringTokenizer(infile.readLine());
            long A = Long.parseLong(st.nextToken());
            long M = Long.parseLong(st.nextToken());
            //solve
            long gcd = gcd(A, M);
            M /= gcd;
            System.out.println(totient(M));
         }
      }
      public static long totient(long n) 
      { 
         long result = n;  
         for (long p = 2; p * p <= n; ++p)
            if (n % p == 0)  
            { 
                while (n % p == 0) 
                    n /= p; 
                result -= result / p; 
            } 
         if (n > 1) 
            result -= result / n; 
         return result; 
      } 
      public static long gcd(long a, long b)
      {
         if(a > b)
         {
            long t = a;
            a = b;
            b = t;
         }
         if(a == 0L)
            return b;
         return gcd(b%a, a);
      }
   }