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.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Main m = new Main();
//		int count = 0;
//		long a = 1;
//		long b = 30;
//		long g = m.gcd(a, b);
//
//		for (int i = 0; i <b; i++) {
//			if (m.gcd(b, a + i) == g) {
//
//				count++;
//			}
//		}
//		System.out.println(count);

		m.func(new Scanner(System.in));

	}

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

	ArrayList<Integer> get_primes(int limit) {
		ArrayList<Integer> res = new ArrayList<>();
		a:
		for (int i = 2; i <= limit; i++) {
			int temp = (int) Math.sqrt(i);

			for (int j = 2; j <= temp; j++) {
				if (i % j == 0) {
					continue a;
				}
			}
			res.add(i);
		}
		return res;
	}

	ArrayList<Long> get_factor(ArrayList<Integer> ps, long x) {

		ArrayList<Long> res = new ArrayList<>();
		for (int y : ps) {
			boolean enter = false;
			while (x % y == 0) {

				enter = true;
				x /= y;
			}
			if (enter) {
				res.add((long) y);
			}
			if (x == 1) {
				return res;
			}
		}
		res.add(x);
		return res;
	}

	int time1(int x) {
		int count = 0;
		for (int i = 0; i < 32; i++) {
			if ((x & (1 << i)) != 0) {
				count++;
			}
		}
		return count;
	}

	long getprod(int x, ArrayList<Long> facs) {
		long res = 1;
		for (int i = 0; i < 32; i++) {
			if ((x & (1 << i)) != 0) {
				res *= facs.get(i);
			}
		}
		return res;
	}

	long count(long x, ArrayList<Long> facs) {

		long res = 0;
		int len = facs.size();
		int s = (1 << len) - 1;
		for (int i = s; i > 0; i = (i - 1) & s) {
			int time_1 = time1(i);
			res += (time_1 % 2 == 0 ? x / (getprod(i, facs)) * -1 : x / (getprod(i, facs)));
		}

		return res;
	}

	void func(Scanner s) {
		int T = s.nextInt();
		ArrayList<Integer> ps = get_primes(100000);

		for (int i = 0; i < T; i++) {
			long a = s.nextLong();
			long b = s.nextLong();
			long g = gcd(a, b);
			a /= g;
			b /= g;
			ArrayList<Long> facs = get_factor(ps, b);
			long temp = count(a + b - 1, facs) - count(a - 1, facs);
			System.out.println(b - temp);
		}
	}

	int[][] temp = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
}

class Node {
	int gap;

	int be;

	public Node(int gap, int be) {
		this.gap = gap;

		this.be = be;
	}
}

