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.*;
import java.io.*;

public class DD {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out, false);
        int t = scanner.nextInt();
        while(t-->0) {
            long a = scanner.nextLong();
            long m = scanner.nextLong();
            long gg = gcd(a, m);
            a/=gg;
            m/=gg;
            long bot = compute(a-1, m);
            long top = compute(a + m-1, m);
            out.println(top - bot);
        }
        out.flush();
    }
    static long compute(long ub, long m) {
        if (ub <1) return 0;
        getFacts(m);
        long ans = ub;
        int sz = facs.size();
        int maxMask =1 << sz;
        for(int mask = 1;mask < maxMask; mask++) {
            long i = 1;
            for(int j = 0; j < facs.size(); j++) {
                if(((1<< j)&mask) > 0)  i*= facs.get(j);
            }
            int cnt = Integer.bitCount(mask);
            if ((cnt & 1) == 1) ans -= ub / i;
            else ans += ub / i;
        }
        return ans;
    }
    static ArrayList<Long> facs;
    static void getFacts(long val) {
        facs = new ArrayList<>();
        for(long v = 2; v * v <= val; v++) {
            if (val % v == 0) {
                while(val % v == 0) {
                    val/=v;
                }
                facs.add(v);
            }
        }
        if (val > 1) facs.add(val);
    }
    static int numFact(long val) {
        int ans = 0;
        for(long v = 2; v * v <= val; v++) {
            if (val % v == 0) {
                while(val % v == 0) {
                    val/=v;
                }
                ans++;
            }
        }
        if (val > 1) ans++;
        return ans;
    }
    static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
