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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DSameGCDs solver = new DSameGCDs();
        solver.solve(1, in, out);
        out.close();
    }

    static class DSameGCDs {
        long a;
        long m;
        boolean[] isPrime;
        ArrayList<Integer> primes;

        public void readInput(Scanner sc) {
            a = sc.nextLong();
            m = sc.nextLong();
        }

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

        public void sieve(int x) {
            isPrime = new boolean[x + 1];
            Arrays.fill(isPrime, true);
            isPrime[0] = isPrime[1] = false;
            primes = new ArrayList<>();
            for (int i = 0; i * i <= x; i++)
                if (isPrime[i])
                    for (int j = i * i; j <= x; j += i)
                        isPrime[j] = false;
            for (int i = 2; i <= x; i++)
                if (isPrime[i])
                    primes.add(i);
        }

        public ArrayList<Long> primeDiv(long a) {
            int idx = 0;
            long p = primes.get(idx++);
            ArrayList<Long> div = new ArrayList<>();
            while (p * p <= a) {
                if (a % p == 0) {
                    div.add(p);
                    while (a % p == 0)
                        a /= p;
                }
                p = primes.get(idx++);
            }
            if (a != 1)
                div.add(a);
            return div;
        }

        public void solve(int testNumber, Scanner sc, PrintWriter pw) {
            int q = sc.nextInt();
            sieve((int) 1e6);
            while (q-- > 0) {
                readInput(sc);
                long gcd = gcd(a, m);
                long div = (m + a - 1) / gcd;
                if (gcd == 1) {
                    pw.println(IncExc(m + a - 1, m) - IncExc(a - 1, m));
                } else {
                    pw.println(IncExc(div, m / gcd) - IncExc((a - 1) / gcd, m / gcd));
                }
            }
        }

        private long IncExc(long div, long m) {
            ArrayList<Long> list = primeDiv(m);
            long ans = div;
            for (int i = 1; i < 1 << list.size(); i++) {
                long mul = 1;
                for (int j = 0; j < list.size(); j++)
                    if ((i & 1 << j) != 0)
                        mul *= list.get(j);
                if (Integer.bitCount(i) % 2 == 1)
                    ans -= div / mul;
                else
                    ans += div / mul;
            }
            return ans;
        }

    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

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

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

    }
}

