#include<cstdio>
#include<vector>
#define LL long long
using namespace std;
int t,cnt,i,j,sign=1;
LL a,b,SOL;
vector<LL> V[100];
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&t);
    V[0].push_back(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(i=3;b>1;i+=2)
        {
            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;
}