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.*;
public class CP {
    public static long gcd(long a,long b){
        if(b==0)
            return a;
        return gcd(b,a%b);
    }
    static ArrayList<Long> list;
    public static long calc(long val){
        int i,j,size=list.size();
        long ans=0;
        for(i=1;i<(1<<size);i++){
            long mul=1;
            int count=0;
            for(j=0;j<size;j++){
                if((i & (1<<j))>0){
                   mul=mul*list.get(j);
                   count++;
                }
            }
            if(count%2==0)
                ans=ans-(val/mul);
            else
                ans=ans+(val/mul);

        }
        //System.out.println(val+" "+(val+1-ans));
        return val+1-ans;
    }
    public static void main(String args[]) throws Exception {
        FastReader in=new FastReader(System.in);
        StringBuilder sb=new StringBuilder();
        int i,j,x;
        int t=in.nextInt();
        while(t-->0) {
           long a=in.nextLong();
           long m=in.nextLong();
           long temp=m;
           long gcd=gcd(a,m);
            //System.out.println(gcd);
           m=m/gcd;
           list=new ArrayList<>();
           long c=2;
           while(c*c<=m){
               if(m%c==0){
                  // if(gcd%m!=0)
                    list.add((long)c);
                   while(m%c==0)
                       m=m/c;
               }
               c++;
           }
            //System.out.println(t);
           if(m!=1)
               list.add(m);
            //System.out.println(list);
           sb.append(calc((a+temp-1)/gcd)-calc((a-1)/gcd)).append("\n");
            //System.out.println(t);


        }
        System.out.println(sb);



    }
}
class FastReader {

    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;

    FastReader(InputStream is) {
        in = is;
    }

    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }

    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    String nextLine() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c != 10 && c != 13; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    char nextChar() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        return (char) c;
    }

    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }

    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}