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 C {

	static long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int tc = sc.nextInt();
		while (tc-- > 0) {
			long a = sc.nextLong(), m = sc.nextLong(), gcd = gcd(a, m);
			long x = a / gcd, y = m / gcd;
			long l = x, r = x + y - 1;
			long ans = r - l + 1;
			ArrayList<Long> primeDiv = fac(y);
			int sz = primeDiv.size();
			for (int msk = 1; msk < 1 << sz; msk++) {
				long remove = 1;
				for (int i = 0; i < sz; i++)
					if ((msk & 1 << i) > 0)
						remove *= primeDiv.get(i);
				long curr = r / remove;
				curr -= (l - 1) / remove;
				if (Integer.bitCount(msk) % 2 == 1)
					ans -= curr;
				else
					ans += curr;

			}
			out.println(ans);

		}
		out.close();

	}

	static ArrayList<Long> fac(long x) {
		ArrayList<Long> primeDiv = new ArrayList();
		for (long d = 2; d * d <= x; d++) {
			if (x % d == 0) {
				primeDiv.add(d);
				while (x % d == 0)
					x /= d;
			}
		}
		if (x > 1)
			primeDiv.add(x);
		return primeDiv;
	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		String nextLine() throws IOException {
			return br.readLine();
		}

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

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

		boolean ready() throws IOException {
			return br.ready();
		}

	}

	static void sort(int[] a) {
		shuffle(a);
		Arrays.sort(a);
	}

	static void shuffle(int[] a) {
		int n = a.length;
		Random rand = new Random();
		for (int i = 0; i < n; i++) {
			int tmpIdx = rand.nextInt(n);
			int tmp = a[i];
			a[i] = a[tmpIdx];
			a[tmpIdx] = tmp;
		}
	}

}