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

import static java.lang.Math.*;

public class Main {
    long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    void run() throws IOException {
        int t = nextInt();
        while (t-- > 0) {
            long a = nextLong();
            long b = nextLong();
            b /= gcd(a, b);
            ArrayList<Long> del = new ArrayList<>();
            long c = b;
            for (long i = 2; i <= sqrt(b); i++) {
                if (c % i == 0) del.add(i);
                while (c % i == 0) c /= i;
            }
            if (c != 1) del.add(c);
            for (Long k : del) {
                b /= k;
                b *= k - 1;
            }
            pw.println(b);
        }
        pw.close();
    }

    class Point {
        long x, y;

        public Point(long a, long b) {
            x = a;
            y = b;
        }
    }

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //BufferedReader br = new BufferedReader(new FileReader("qual.in"));

    StringTokenizer st = new StringTokenizer("");
    PrintWriter pw = new PrintWriter(System.out);
    //PrintWriter pw = new PrintWriter("qual.out");

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

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

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

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

    public Main() throws FileNotFoundException {
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    long mod = Integer.MAX_VALUE;

}