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.
//////package random_practiceQuestions;


import java.io.*;
import java.util.*;

public class D1295 {
    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        String next() { // reads in the next string
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() { return Integer.parseInt(next()); } // reads in the next int
        public long nextLong() { return Long.parseLong(next()); } // reads in the next long
        public double nextDouble() { return Double.parseDouble(next()); } // reads in the next double
    }
    static InputReader r = new InputReader(System.in);
    static PrintWriter pw = new PrintWriter(System.out);
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args){
        int q=r.nextInt();
        for (int i=0;i<q;i++){
            long a=r.nextLong();
            long b=r.nextLong();
            long c=gcd(a,b);

            long x=a/c;
            long y=b/c;
            long z=y;

            //phi(y) is the answer

            long ans=y;
            for (int j=2;j<=Math.sqrt(z);j++){
                if (y%j==0){
                    ans=ans*(j-1)/j;
                    while (y%j==0){
                        y=y/j;
                    }
                }
            }
            if (y>1){
                ans=ans/y*(y-1);
            }
            if (ans==z){
                System.out.println(ans-1);
            }
            else{
                System.out.println(ans);
            }

        }

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