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

public class d {
	// no duplicates
	List<Long> prime_f(long n) {
		List<Long> primef = new ArrayList<>();
		for(long i = 2 ; i * i <= n ; i++) {
			if(n % i == 0) {
				primef.add(i);
				while(n % i == 0) {
					n /= i;
				}
			}
		}
		if(n > 1) primef.add(n);
		return primef;
	}
	long solve(long bound, List<Long> primes) {
		if(bound == 0) return 0;
		long total = 0;
		for(int i = 0 ; i < (1 << primes.size()) ; i++) {
			long x = 1;
			for(int j = 0 ; j < primes.size() ; j++)
				if((i & (1 << j)) > 0)
					x *= primes.get(j);
			if(Integer.bitCount(i) % 2 == 0) total += (bound / x);
			else total -= (bound / x);
		}
		return total;
	}
	long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
	public d() {
		FS scan = new FS();
		PrintWriter out = new PrintWriter(System.out);
		int tc = scan.nextInt();
		for(int tt = 0 ; tt < tc ; tt++) {
			long a = scan.nextLong();
			long m = scan.nextLong();
			long g = gcd(a, m);
			
			long y = m / g;
			
			List<Long> primes = prime_f(y);
			
			
			long left = solve((a - 1) / g, primes);
			long right = solve((a + m - 1) / g, primes);
			out.println(right - left);
		}
		out.close();
	}
	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() {
			while(!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) { e.printStackTrace(); }
			}
			return st.nextToken();
		}
		public int nextInt() { return Integer.parseInt(next()); }
		public long nextLong() { return Long.parseLong(next()); }
		public double nextDouble() { return Double.parseDouble(next()); }
	}
	public static void main(String[] args) throws Exception { new d(); }
}
/*



*/