#include<cstdio>
#include<vector>
#include<bitset>
#include<iostream>
#define LL long long
using namespace std;
long long t,cnt,sign=1,nr,k;
long long a,b,SOL,i,j;
int C[100010];
bitset<1000010>B;
vector<long long> 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;
        k=2*i;
        for(j=i*i;j<=1000000;j+=k)B[j]=1;
    }
    for(;t;--t)
    {
        scanf("%lld%lld",&a,&b);
        SOL=a;
        for(k=1;(long long)(C[k]*C[k])<=b&&k<=nr;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);
        }
        if(b>1)
        {
            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)*b);
        }
        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;
}