#include <bits/stdc++.h>
 
using namespace std;
 
int i,n,a,b,ciur[100500],j,CIUR,D[300],d,rs;
bool e[1000005];
 
int main()
{
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    for (i=2; i<=1000000; i++)
        if (!e[i])
            for (j=2; j<=1000000/i; j++)
                e[i*j]=true;
    for (i=2; i<=1000000; i++)
        if (!e[i]) ciur[++CIUR]=i;
    cin>>n;
    for (i=1; i<=n; i++)
    {
        cin>>a>>b;
        d=rs=0;
        for (j=1; ciur[j]<=sqrt(b); j++)
        {
            if (b%ciur[j]==0) 
            {
                D[d++]=ciur[j];
                while (b%ciur[j]==0) b/=ciur[j];
            }
        }
        if(b>1) D[d++] = b;
        for (int j=1; j<(1<<d); j++)
        {
            int k=0,pr=1,semn=-1;
            for (int z=0; z<d; z++) if ((1<<z)&j) pr*=D[z],k++;
            if (k%2) semn=1;
            rs+=(a/pr)*(semn);
        }
        cout<<a-rs<<'\n';
    }
}