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.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class D {
    public static ArrayList<Integer> primes(long N) {
        int sqrt = (int) Math.sqrt(N);
        boolean[] a = new boolean[sqrt+1];
        Arrays.fill(a, true);
        a[1] = false;
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i=2; i<a.length; i++) {
            if (a[i]) {
                ans.add(i);
                for (int j=i*2; j<a.length; j+=i)
                    a[j] = false;
            }
        }
        return ans;
    }
    public static long gcd(long a, long b) {
        if (a>b) return gcd(b,a);
        if (a==0) return b;
        return gcd(b%a, a);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        ArrayList<Integer> pr = primes(10000000000L);
        int T = in.nextInt();
        for (int ti=0; ti<T; ti++) {
            long a=in.nextLong();
            long m=in.nextLong();
            long gcd = gcd(a, m);
            long mq=m/gcd;
            long ans = mq;
            boolean divisible = false;
            for (int p : pr) {
                if (mq % p == 0) {
                    while (mq%p==0) mq /= p;
                    ans = ans / p * (p-1);
                    divisible=true;
                }
            }
            if (mq > 1) {
                ans = ans / mq * (mq-1);
            }
            System.out.println(ans);
        }
    }
}
