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.
//Same GCD's
import java.io.*;
import java.util.*;

public class D1295{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      int t = Integer.parseInt(f.readLine());
      
      for(int q = 0; q < t; q++){
      
         StringTokenizer st = new StringTokenizer(f.readLine());
      
         long a = Long.parseLong(st.nextToken());
         long m = Long.parseLong(st.nextToken());
         
         long gcd = gcd(a,m);
         //out.println(gcd);
         
         //find totient of m/gcd
         long tot = totient(m/gcd);
         out.println(tot);
         
      }
      
      
      
      
      
      
      
      out.close();
   }
   //from cp-algorithms
   public static long totient(long x){
      long result = x;
      for(long i = 2; i*i<=x; i++){
         if(x%i == 0){
            while(x%i == 0){
               x/=i;
            }
            result -= result/i;
         }
      }
      
      if(x > 1){
         result -= result/x;
      }
      return result;
   }
   
   //gcd of two numbers, a and b
   public static long gcd(long a, long b){
      
      if(b > a){
         long temp = a;
         a = b;
         b = temp;
      }
      
      
      
      while(a != 0){
         b = b%a;
         
         long temp = a;
         a = b;
         b = temp;
         
      }
      
      return b;
   }
         
   
   
   
}