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.
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
public class realfast implements Runnable {
    private static final int INF = (int) 1e9;
 
    public  void solve() throws IOException 
    {
     
     int t = readInt();
     for(int f =0;f<t;f++)
     {
      long a = readLong();
      long m = readLong();
      long gcd = gcd(a,m);
      a=a/gcd;
      m=m/gcd;
      long val=1;
      int i=2;
      long m1=m;
      int root=(int)Math.pow(m,0.5);
      long arr[]= new long[15];
      int count=-1;
      while((m!=1)&&(i<=root))
      {
      	if(m%i==0){
      	count++;
      	arr[count]=i;
        }
      	while((m%i)==0)
      	{
      		m=m/i;
      	}
      	
      	i++;
      }
      
      if(m>=2)
      {
       count++;
       arr[count]=m;	
      }
      int fin = (int)Math.pow(2,count+1)-1;
      long ans=0;
      for(int j=1;j<=fin;j++)
      {
       long cur	= 1;
       int pow=1;
       int lo=0;
       int even=0;
       while(lo<=count)
       {
       	if((pow&j)!=0){
       	cur=cur*arr[lo];
       	
       	even++;

       }
       	pow=pow*2;
       	lo++;
       	
       }
       if(even%2==1)
       ans = ans+ m1/cur;
       else
       ans=ans- m1/cur;
      }
      
      out.println(m1-ans); 
      
      	
     }

    }    
    public long gcd(long a , long b)
    {
     if(a<b)
     {
     	long t =a;
     	a=b;
     	b=t;
     }
     if(a%b==0)
     return b;
     return gcd(b,a%b);	
    }
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    int u ;
    int v ;
    int val;
    edge(int u1, int v1 , int val1)
    {
       this.u=u1;
       this.v=v1;
       this.val=val1;
    }
    public int compareTo(edge e)
    {
        return this.val-e.val;
    }
}