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 CF1295D extends PrintWriter {
	CF1295D() { super(System.out); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1295D o = new CF1295D(); o.main(); o.flush();
	}

	long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}
	void main() {
		int t = sc.nextInt();
		while (t-- > 0) {
			long a = sc.nextLong();
			long m = sc.nextLong();
			long d = gcd(a, m);
			m /= d;
			long totient = m;
			for (int p = 2; p <= m / p; p++)
				if (m % p == 0) {
					totient = totient / p * (p - 1);
					while (m % p == 0)
						m /= p;
				}
			if (m > 1)
				totient = totient / m * (m - 1);
			println(totient);
		}
	}
}
