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

public class D
{

    static long gcd(long a, long b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }

    static void solve(FastIO io)
    {
        long a = io.nextLong();
        long b = io.nextLong();
        
        long k = b / gcd(a, b);

        HashSet<Long> fac = new HashSet<>();

        long x = k;

        for (long i = 2; i * i <= x; i++)
        {
            if (x % i != 0)
                continue;

            fac.add(i);
            
            while (x % i == 0)
                x /= i;
        }

        if (x != 1)
            fac.add(x);

        long phi = k;


        for (long i : fac)
            phi = phi - (phi / i);

        io.println(phi);
    }

    public static void main(String[] args) 
    {
        FastIO io = new FastIO();

        int t = io.nextInt();
        for (int i = 0; i < t; i++)
            solve(io);

        io.close();
    }

    static class FastIO extends PrintWriter
    {
        StringTokenizer st = new StringTokenizer("");
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

        FastIO()
        {
            super(System.out);
        }

        String next()
        {
            while (!st.hasMoreTokens())
            {
                try {
                    st = new StringTokenizer(r.readLine());
                } catch (Exception e) { }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }
    }
}