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.IOException;
import java.io.InputStream;
import java.util.Scanner;
import java.util.StringTokenizer;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
 
public class Main {
    static int maxn = (int)(1e5 + 5);
    static long gcd(long x, long y) {
    	while(true) {
    		long z = x%y;
    		if(z == 0) {
    			break;
    		}
    		x = y; y = z;
    	}
    	return y;
    }
    static long eular(long x) {
    	long ret = x, t = x;
    	for(long j = 2; j*j <= x; ++j) {
    		if(t%j == 0) {
    			ret = ret/j*(j - 1);
    			while(t%j == 0) {
    				t /= j;
    			}
    		}
    	}
    	if(t > 1) {
    		ret = ret/t*(t - 1);
    	}
    	return ret;
    }
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(System.out);
//        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for(int cs = 1; cs <= T; ++cs) {
        	long a = in.nextLong();
        	long m = in.nextLong();
        	long d = gcd(a, m);
        	out.println(eular(m/d));
        }
        out.flush();
//        in.close();
    }
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        public String next() {
            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());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}

/*


0 1 2 3 4 5 6 7 8 9
6 2 5 5 4 5 6 3 7 6

*/
  	 			   	  	  				  		  	 			