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.Scanner;


public class SameGcds 
{
 	
	public static void main(String[] args) 
	 {
		Scanner scan=new Scanner(System.in);
		
		int t=scan.nextInt();
	    while(t-->0)
	     {
	    	long a=scan.nextLong();
	    	long m=scan.nextLong();
	    	if(a>m) 
	    	{
	    		long temp=a;
	    		a=m;
	    		m=temp;
	    	}
	    	m=m/gcd(a,m);
	    	if(isPrime2(m)) 
	    	{
	    		System.out.println(m-1);
	    	}
	    	else
	    	{
	    	System.out.println(eulerTotient(m));
	    
	    	}
	    	
	     }
	     scan.close();
	 
	 }
	
	static long eulerTotient(long num) 
	{
		long n=num;;
		long res=num;
		for(long i=2;i*i<=num;i++)
		  {
			if(n%i==0) 
			{
			 while(n%i==0) 
			  {
				n/=i;
			  }
			  res=res/i;
			  res=res*(i-1);
		
			}
		  }
		if(n>1) 
		  {
			res=res/n;
			res=res*(n-1);
		  }
	    return res;
	}
	static long gcd(long a ,long b) 
	{
		if(b==0)return a;
		return gcd(b,a%b);
		
	}
	static boolean isPrime2(long num)
	{
		if(num<2) 
		{
			return false;
		}
		else if(num==2) 
		{
			return true;
		}
		if(num%2==0) 
		{
			return false;
		}
		else
		{
		   long limit=(long) Math.sqrt(num);
		   for(int i=3;i<=limit;i+=2) 
		   {
			   if(num%i==0) 
			   {
				   return false;
			   }
		   }
		}
		return true;
	}
}
