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.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        new Main().run();}


    int ct = 0;
    void add(int u,int v){
        to[ct] = v;
        ne[ct] = h[u];
        h[u] = ct++;
    }
    int stk[];
    int pa[];
    int h[],to[],ne[];
    int dis[];
    int time[];
    int clock =0;
    int vale[][];
    int vals[][];
    int valerm[][];
    int valsrm[][];
    int ups[];
    int res[];
    int downs[];
    int cnt_up[];
    int cnt_down[];
    int myup[];
    int mydown[];
    int fa[];

    int root(int x){
        if(fa[x]==x){
            return x;
        }else{
            int pt = x;
            while(pt!=fa[pt]){
                pt = fa[pt];
            }
            while(x!=fa[x]){
                int cur = x;
                x = fa[x];
                fa[cur] = pt;
            }
            return pt;
        }
    }

    void dfs(int rt){
        int p = 0;
        stk[p++] = 0;
        while(p>0){
            rt = stk[--p];
            if(rt>=0){
                stk[p++] = ~rt;
                cnt_up[rt] = ups[myup[rt]];
                cnt_down[rt] = downs[mydown[rt]];
                for(int i=h[rt];i!=-1;i=ne[i]){
                    int v =to[i];
                    if(v==pa[rt]) continue;
                    stk[p++] = v;
                }
            }else{
                rt = ~rt;
                for(int cao:vals[rt]){
                    ups[cao]++;
                }
                for(int cao:vale[rt]){
                    downs[cao]++;
                }
                for(int cao:valerm[rt]){
                    downs[cao]--;
                }
                res[rt] += ups[myup[rt]]-cnt_up[rt] + downs[mydown[rt]]-cnt_down[rt];
                for(int cao:valsrm[rt]){
                    ups[cao]--;
                }
            }
        }
    }




    void solve(){
        int q = ni();
        long prime[] = new long[20];
        ot:for(int ii=0;ii<q;++ii){
            long a = nl();
            long m = nl();
            long g = gcd(a,m);
            a /= g; m /= g;

            BigInteger z1 = BigInteger.valueOf(m);
            int p= 0 ;

            for(long ck=2;ck*ck<=m;++ck){
                    if(m%ck==0) {
                    while (m % ck == 0) {
                        m /= ck;
                    }
                    prime[p++] = ck;
                }
            }
            if(m>1){
                prime[p++] = m;
            }
            long s = 1;
            long x = 1;
            for(int j=0;j<p;++j){
                s *= (prime[j]-1);
                x *= prime[j];
            }

            println(z1.multiply(BigInteger.valueOf(s)).divide(BigInteger.valueOf(x)));




        }


    }



    int n = 0;
    void solve1() {
        n  = ni();
        int m  = ni();
        int es = 2*(n-1);
        pa = new int[n];
        fa = new int[n];
        ups = new int[2*n+1];
        downs = new int[2*n+1];
        h = new int[n];
        dis = new int[n];
        stk = new int[n];
        Arrays.fill(h,-1);
        to = new int[es];
        ne = new int[es];
        time = new int[n];
        res = new int[n];
        myup = new int[n];
        mydown = new int[n];
        cnt_up = new int[n];
        cnt_down = new int[n];
        for(int i=0;i<n-1;++i){
            int u = ni()-1;
            int v = ni()-1;
            add(u,v);
            add(v,u);
        }
        for(int i=0;i<n;++i){
            time[i] = ni();
        }
        int u[] = new int[m];
        int v[] = new int[m];
        int le[]  = new int[n];
        int ls[]  = new int[n];
        int q[] = new int[n];
        for(int i=0;i<m;++i) {
            u[i] = ni() - 1;
            v[i] = ni() - 1;
            le[v[i]]++;
            ls[u[i]]++;
            q[v[i]]++;
            q[u[i]]++;
        }
        int qy[][] = new int[n][];
        for(int i=0;i<n;++i){
            qy[i] = new int[q[i]];
            fa[i] = i;
        }
        int oq[] = q.clone();
        for(int i=0;i<m;++i) {
            qy[u[i]][--q[u[i]]] = v[i];
            qy[v[i]][--q[v[i]]] = u[i];
        }
        int rt = 0;
        int p = 1;
        boolean vis[] = new boolean[n];
        stk[0] = 0;
        while(p>0) {
            rt = stk[--p];
            if(rt>=0) {
                stk[p++] = ~rt;
                for (int i = h[rt]; i != -1; i = ne[i]) {
                    int vv = to[i];
                    if (pa[rt] == vv) continue;
                    pa[vv] = rt;
                    dis[vv] = 1 + dis[rt];
                    stk[p++] = vv;
                }
            }else{
                rt = ~rt;
                vis[rt] = true;
                for (int i = 0 ;i < qy[rt].length;++i) {
                    if (vis[qy[rt][i]]) {
                        qy[rt][i] = root(qy[rt][i]);
                    }else{
                        qy[rt][i] = -1;
                    }
                }
                fa[rt] = pa[rt];
            }
        }
        for(int i=0;i<n;++i){
            myup[i] = dis[i]+time[i];
            mydown[i] = time[i]-dis[i]+n;
        }
        int lca[] = new int[m];
        int v1[] = new int[m];
        int lcas[] = new int[n];
        int lcae[] = new int[n];
        for(int i=0;i<m;++i){
            int c1 = qy[u[i]][--oq[u[i]]];
            int c2 = qy[v[i]][--oq[v[i]]];
            if(c1!=-1){
                lca[i] = c1;
            }else{
                lca[i] = c2;
            }
            v1[i] = dis[u[i]]-(dis[lca[i]]<<1)+n;
            lcas[lca[i]]++;
            lcae[lca[i]]++;
        }
        vale = new int[n][];
        vals = new int[n][];
        valsrm = new int[n][];
        valerm = new int[n][];
        for(int i=0;i<n;++i){
            vale[i] = new int[le[i]];
            vals[i] = new int[ls[i]];
            valsrm[i] = new int[lcas[i]];
            valerm[i] = new int[lcae[i]];
        }
        for(int i=0;i<m;++i) {
            valerm[lca[i]][--lcae[lca[i]]] = vale[v[i]][--le[v[i]]] = v1[i];
            valsrm[lca[i]][--lcas[lca[i]]] = vals[u[i]][--ls[u[i]]] = dis[u[i]];
        }
        dfs(0);
        for(int i=0;i<n;++i){
            print(res[i]+" ");
        }



















    }









//    int []h,to,ne,wt;

    long t1[];
    //    long t2[];
    void update(long[] t,int i,long v){
        for(;i<t.length;i+=(i&-i)){
            t[i] += v;
        }
    }
    long get(long[] t,int i){
        long s = 0;
        for(;i>0;i-=(i&-i)){
            s += t[i];
        }
        return s;
    }

    int equal_bigger(long t[],long v){
        int s=0,p=0;
        for(int i=Integer.numberOfTrailingZeros(Integer.highestOneBit(t.length));i>=0;--i) {
            if(p+(1<<i)< t.length && s + t[p+(1<<i)] < v){
                v -= t[p+(1<<i)];
                p |= 1<<i;
            }
        }
        return p+1;
    }


    long gcd(long a,long b){ return b==0?a: gcd(b,a%b);}
    InputStream is;PrintWriter out;
    void run() throws Exception {is = System.in;
      //  is = new FileInputStream("C:\\Users\\Luqi\\Downloads\\P1600_2.in");

        out = new PrintWriter(System.out);solve();out.flush();}
    private byte[] inbuf = new byte[2];
    public int lenbuf = 0, ptrbuf = 0;
    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {lenbuf = is.read(inbuf);} catch (IOException e) {throw new InputMismatchException();}
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];}
    private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}
    private int skip() {int b;while((b = readByte()) != -1 && isSpaceChar(b));return b;}
    private double nd() {return Double.parseDouble(ns());}
    private char nc() {return (char) skip();}
    private char ncc() {int b;while((b = readByte()) != -1 && !(b >= 32 && b <= 126));return (char)b;}
    private String ns() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[] ns(int n) {char[] buf = new char[n];int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) { buf[p++] = (char) b;b = readByte(); }
        return n == p ? buf : Arrays.copyOf(buf, p);}
    private String nline() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b) || b == ' ') { sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[][] nm(int n, int m) {char[][] a = new char[n][];for (int i = 0; i < n; i++) a[i] = ns(m);return a;}
    private int[] na(int n) {int[] a = new int[n];for (int i = 0; i < n; i++) a[i] = ni();return a;}
    private long[] nal(int n) { long[] a = new long[n];for (int i = 0; i < n; i++) a[i] = nl();return a;}
    private int ni() { int num = 0, b; boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9') num = (num << 3) + (num << 1) + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    private long nl() { long num = 0; int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9')  num = num * 10 + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    void print(Object obj){out.print(obj);}
    void println(Object obj){out.println(obj);}
    void println(){out.println();}
}