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.*;
public class GFG {
    public static long gcd(long a,long b)
    {
        if(a==0)
        return b;
        return gcd(b%a,a);
    }
    static long phi(long n) 
{ 
    // Initialize result as n 
    long result = n;  
  
    // Consider all prime factors  
    // of n and subtract their 
    // multiples from result 
    for (long p = 2; p * p <= n; ++p) 
    { 
          
        // Check if p is  
        // a prime factor. 
        if (n % p == 0)  
        { 
              
            // If yes, then update 
            // n and result 
            while (n % p == 0) 
                n /= p; 
            result -= result / p; 
        } 
    } 
  
    // If n has a prime factor 
    // greater than sqrt(n) 
    // (There can be at-most  
    // one such prime factor) 
    if (n > 1) 
        result -= result / n; 
    return result; 
} 
   public static void main (String[] args) {
		Scanner sc=new Scanner(System.in);
	    int t1=sc.nextInt();
	    while (t1-->0)
	    {
	        long a=sc.nextLong();
	        long m=sc.nextLong();
	        long g=gcd(a,m);
	        long k=m/g;
	        System.out.println(phi(k));
	        
	    }
   }
}