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.util.*;
import java.io.*;
public class Task{
static long gcd(long a,long b){if(b==0){return a;}return gcd(b,a%b);}
  static long phi(long n){
  	int k=(int)Math.sqrt(n);
  	long x=1,y=n;
  	for(int i=2;i<=k;i++){
  		boolean b=false;
  		while(n%i==0){
  			n/=i;b=true;
  		}
  		if(b){
  			 y/=i;
  		x*=(long)(i-1);
  		}
  	}
  	if(n>1){x*=(n-1);y/=n;}
  	return x*y;
  }

public static void main(String[] args) throws FileNotFoundException, IOException{
       Scanner s=new Scanner(System.in);
       BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));
       	StringBuilder sb=new StringBuilder();
       	int q=s.nextInt();
       	while(q--!=0){
       		long a=s.nextLong(),b=s.nextLong();
       		long x=gcd(a,b);
       		a/=x;b/=x;
       		long res=phi(b);
       		out.write(res+"\n");   		
       	}
       
          out.flush();
       	}
       }
        
  
 