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 Solution
{
       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 t  = sc.nextInt();
              while(t-- > 0)
              {
              long a = sc.nextLong();
              long m = sc.nextLong();
              m = m/gcd(a,m);
              System.out.println(phi(m));
              }
       }
}