#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
vector<int>nrprim,divizors;
bitset<1000001>ap;
int m,lenght,opmax,howmany;
unsigned long long a,b,prod;
long long solve(int pos,int last)
{
    if(pos==opmax)
        return (a-1)/prod;
    long long s=0;
    for(int j=last+1;j<=howmany-opmax+pos;j++)
    {
        prod*=divizors[j];
        s+=solve(pos+1,j);
        prod/=divizors[j];
    }
    return s;
}
void solve()
{
    divizors.clear();
    long long copb=b;
    for(int i=0;i<lenght;i++)
    {
        if(copb%nrprim[i]!=0)
            continue;
        while(copb%nrprim[i]==0)copb/=nrprim[i];
        divizors.push_back(nrprim[i]);
        if(copb==1)
            break;
    }
    howmany=divizors.size();
    long long rez=a-1;
    int k=-1;
    prod=1;
    for(int i=1;i<=howmany;i++)
    {
        opmax=i;
        rez+=k*solve(0,-1);
        k*=-1;
    }
    fout<<rez<<"\n";
}
void make_prime()
{
    for(int i=2;i<=1000000;i++)
    {
        if(ap[i])
            continue;
        nrprim.push_back(i);
        int j=2*i;
        while(j<=1000000)
        {
            ap[j]=1;
            j+=i;
        }
    }
    lenght=nrprim.size();
}
int main()
{
    fin>>m;
    make_prime();
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b;
        solve();
    }
    return 0;
}