#include<cstdio>
#include<vector>
#include<bitset>
#define LL long long
using namespace std;
int t,cnt,j,sign=1,C[100010],nr,k;
LL a,b,SOL,i;
bitset<1000010>B;
vector<LL> V[100];
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&t);
    V[0].push_back(1);
    C[1]=2;nr=1;
    for(i=3;i<=1000000;i+=2)
    {
        if(B[i]==1)continue;
        C[++nr]=i;
        for(j=i;j<=1000000;j+=i)B[j]=1;
    }
    for(;t;--t)
    {
        scanf("%lld%lld",&a,&b);
        SOL=a;
        if(!(b%2)){while(!(b%2))b/=2;V[1].push_back(2);cnt=1;}
        for(k=1;b>1;k++)
        {
            i=C[k];
            if(b%i)continue;
            while(!(b%i))b/=i;
            cnt++;
            for(j=cnt-1;j>=0;j--)for(vector<LL>::iterator it=V[j].begin();it!=V[j].end();it++)V[j+1].push_back((*it)*i);
        }
        for(j=1;j<=cnt;j++)
        {
            if(j&1)sign=-1; else sign=1;
            for(vector<LL>::iterator it=V[j].begin();it!=V[j].end();it++)SOL+=sign*(a/(*it));
            V[j].resize(0);
        }
        printf("%lld\n",SOL);
    }
    return 0;
}