#include <bits/stdc++.h>

using namespace std;

ifstream fin  ("pinex.in");
ofstream fout ("pinex.out");

const int LIM = 1000000;
bitset <LIM + 5> ok;
int prim, p[80005];

int semn[]={-1, 1};
long long t, a, b, sol;
long long m, e, d[100];

void bt(int k, long long crt, int lst){
    if(k > 1){
        sol += (a/crt) * semn[(k-1)%2];
        if(k > m)
            return;
    }

    for(int i=lst+1; i<=m; i++)
        bt(k+1, 1LL*crt*d[i], i);
}

int main (){
    ok[0]=ok[1]=1;
    for(int i=4; i<=LIM; i+=2)
        ok[i]=1;
    for(int i=3; i<=LIM/i; i+=2)
        if(ok[i] == 0)
            for(int j=i*i; j<=LIM; j+=i)
                ok[j]=1;

    p[++prim]=2;
    for(int i=3; i<=LIM; i+=2)
        if(ok[i] == 0)
            p[++prim]=i;

    fin>>t;
    for(int test=1; test<=t; test++){
        fin>>a>>b;
        m=0; sol=0;

        for(int i=1; p[i] <= b / p[i]; i++){
            e=0;
            while(b%p[i] == 0){
                e=1;
                b/=p[i];
            }
            if(e != 0)
                d[++m]=p[i];
        }
        if(b != 1)
            d[++m]=b;

        bt(1, 1, 0);
        fout<<a-sol<<"\n";
    }
    return 0;
}