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 Main {
	// taken from
	// https://www.geeksforgeeks.org/eulers-totient-function/
	static long gcd(long a, long b)
	{
		if(a==0 || b==0)
			return a+b;
		return gcd(b,a%b);
	}
	static long phi(long n) 
	{
		long result = n;  
		for (long p = 2; p * p <= n; ++p) 
		{ 
			if (n % p == 0)  
			{
				while (n % p == 0) 
				    n /= p; 
				result -= result / p;
			} 
		}
		if (n > 1) 
		    result -= result / n; 
		return result; 
	}
	public static void main(String[] args)throws IOException {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        
		int t = in.nextInt();
		long a,m;
		for(int i=0;i<t;i++)
		{
			a=in.nextLong();
			m=in.nextLong();
			// out.println("gcd"+m/gcd(a,m));
			out.println(phi(m/gcd(a,m)));
		}
        out.close();
	}
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

    }

}