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.StringTokenizer;

public class D {

    FastScanner scanner;
    PrintWriter writer;

    void solve() throws IOException {
        scanner = new FastScanner(System.in);
        writer = new PrintWriter(System.out);

        int tests = scanner.nextInt();

        for (int t = 0; t < tests; t++) {
            long a = scanner.nextLong();
            long m = scanner.nextLong();

            long g = gcd(a, m);

            writer.println(phi(m / g));
        }

        writer.close();
    }

    private long phi(long x) {
        long phi = x;
        for (long i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                while (x % i == 0) {
                    x /= i;
                }
                phi -= phi / i;
            }
        }
        if (x > 1)
            phi -= phi / x;
        return phi;
    }

    long gcd(long a, long b) {
        while (a > 0 && b > 0) {
            if (a > b) {
                a = a % b;
            } else {
                b = b % a;
            }
        }
        return a + b;
    }

    public static void main(String... args) throws IOException {
        new D().solve();
    }

    static class FastScanner {

        BufferedReader br;
        StringTokenizer tokenizer;

        FastScanner(String fileName) throws FileNotFoundException {
            this(new FileInputStream(new File(fileName)));
        }

        FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

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

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

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

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