#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long m,rsp,a,b,contor,prime[1000000],v[1000];
bool ciur[1000001];
int main()
{
    for(int i=2;i<=1000000;++i)
        if(!ciur[i])
    {contor++;
        prime[contor]=i;
        for(int j=2*i;j<1000000;++j)
            ciur[j]=1;
    }
    fin>>m;
    for(int i=1;i<=m;++i)
    {
       fin>>a>>b;
        int j=1,nr=0;
        while(b>1 && prime[j]*prime[j]<=b)
        {
            if(b%prime[j]==0)
            {
                v[++nr]=prime[j];
                while(b%prime[j]==0)b/=prime[j];
            }
            ++j;
        }
        if(b>1)
            v[++nr]=b;
        rsp=a;
        for(j=1;j<(1LL<<nr);++j)
        {
            int ne=0;
            int p=1;
            for(int d=0;d<nr;++d)
                if(j & (1LL<<d))
            {
                ne++;
                p*=v[d+1];
            }
            if(ne%2) rsp-=a/p;
            else rsp+=a/p;
        }
    fout << rsp << '\n';
    }
    return 0;
}