#include <fstream>
using namespace std;

#define N 1005000

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

int p[N/2], k, nr, q;
long long fac[100], a, b, sol;
bool bo[N];

void ciur()
{
    p[++k]=2;
    for(int i=2;i<=N;i+=2) bo[i]=1;
    int i;
    for(i=3;i*i<=N;i+=2)
    {
        if(!bo[i])
        {
            p[++k]=i;
            for(int j=i*i;j<=N;j+=i) bo[j]=1;
        }
    }
    for(;i<=N;i+=2)
        if(!bo[i]) p[++k]=i;
}

int main()
{
    fin>>q;
    ciur();
    while(q--)
    {
        fin>>a>>b;
        nr=0;
        sol=0;
        for(int i=1;p[i]<=b&&i<=k;++i)
        {
            if(b%p[i]==0)
            {
                fac[++nr]=p[i];
                while(b%p[i]==0) b/=p[i];
            }
        }
        int cnt, pr;
        if(b>1) fac[++nr]=b;
        for(int i=1;i<=(1<<nr);++i)
        {
            cnt=0, pr=1;
            for(int j=0;j<nr;++j)
                if(i&(1<<j)) pr*=fac[j+1], cnt++;
            if(cnt%2) sol-=a/pr;
            else sol+=a/pr;
        }
        fout<<sol<<"\n";
    }
    return 0;
}