#include <fstream>
#include <bitset>
using namespace std;
long long t,n,i,j,k,d,p,ap,e,sol,prod,a,b;
long long v[10001],f[100001],w[10001];
bitset <1000001> ciur;
ifstream fin ("pinex.in");
ofstream fout ("pinex.out");

int main (){

    for (i=2;i<=1000000;i++){
        if (ciur[i] == 0){
            f[++k] = i;
            for (j=2*i;j<=1000001;j+=i)
                ciur[j] = 1;
        }
    }

    fin>>t;
    for (;t--;){
        fin>>a>>b;
        /// il descompunem pe b in factori primi
        d = 1;
        p = b;
        k = 0;
        sol = 0;
        while (p!=1 && f[d]*f[d] <= p){
            e = 0;
            while (p % f[d] == 0){
                p/=f[d];
                e++;
            }
            if (e != 0)
                v[++k] = f[d];
            d++;
        }
        if (p != 1)
            v[++k] = p;
        for (i=0;i<=k;i++)
            w[i] = 0;
        while (w[0] == 0){
            i = k;
            while (w[i] == 1){
                w[i] = 0;
                i--;
            }
            w[i] = 1;
            prod = 1;
            ap = 0;
            for (i=1;i<=k;i++)
                if (w[i] == 1){
                    ap++;
                    prod *= v[i];
                }
            if (ap % 2 == 0)
                sol += a/prod;
            else
                sol -= a/prod;
        }
        fout<<sol<<"\n";
    }


    return 0;
}