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 SameGCDs {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		int T = Integer.parseInt(in.readLine());
		for(int i = 0; i < T; ++i) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			long A = Long.parseLong(st.nextToken());
			long M = Long.parseLong(st.nextToken());
			long gcd = gcd(A, M);
			long below = (A - 1) / gcd;
			long above = (A + M - 1) / gcd;
			long mLeft = M / gcd;
			for(int j = 2; j <= Math.sqrt(M) && mLeft != 1; ++j) {
				boolean isFactor = false;
				while(mLeft % j == 0) {
					mLeft /= j;
					isFactor = true;
				}
				if(isFactor) {
					below -= below / j;
					above -= above / j;
				}
			}
			if(mLeft != 1) {
				below -= below  / mLeft;
				above -= above  / mLeft;
			}
			out.println(above - below);
		}
		in.close();
		out.close();
	}
	static long gcd(long a, long b) {
		if(b == 0) {
			return a;
		} else {
			return gcd(b, a % b);
		}
	}
}