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.*;
import java.io.*;

public class two {

	// https://codeforces.com/contest/1295/problem/D
	
	public static void main(String[] args) throws IOException, FileNotFoundException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		//BufferedReader in = new BufferedReader(new FileReader("SameGCDs"));

		int t = Integer.parseInt(in.readLine());
		while (t --> 0) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			long a = Long.parseLong(st.nextToken());
			long b = Long.parseLong(st.nextToken());
			long gcd = gcd(a,b);
			a /= gcd;
			b /= gcd;
			gcd = gcd(a,b);
			//if (gcd!=1) System.out.println(b/gcd - 1);
			//else {
				long totient = totient(b);
				System.out.println(totient);
			//}
		}
	}
	
	public static long totient(long n) {
		long ret = 1;
		if (n%2 == 0) {
			n>>=1;
			while (n%2 == 0) {
				n >>=1;
				ret *= 2;
			}
		}
        for (long i = 3; i*i<=n; i+=2)  { 
            if (n%i==0) { 
                ret *= (i-1);
                n /= i;
                while (n%i == 0) {
                	ret *= i;
                	n/=i;
                }
            } 
        }
        if (n!=1) {
        	ret *= (n-1);
        }
		return ret;
	}
	
	public static long gcd(long a, long b) {
		if (a == 0) return b;
		if (b == 0) return a;
		return gcd(b, a%b);
	}

}
