#include <fstream>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bool v[32000];
int prime[3500];
int div[300];
int g[300];
int i,j,k,n,a,b,d,aux,nr,t;
int main(){
    for(i=2;i<32000;i++)
        if(v[i]==0){
            for(j=i+i;j<32000;j+=i)
                v[j]=1;
            prime[++k]=i;
        }
    fin>>n;
    for(;n--;){
        fin>>a>>b;
        i=0;
        int total=0;
        for(d=1;prime[d]<=b/prime[d] && b>1 && d<=k;d++)
            if(b%prime[d]==0){
                div[++i]=prime[d];
                while(b%prime[d]==0)
                    b/=prime[d];
        }
        if(b>1)div[++i]=b;
        for(j=0;j<=i+1;j++)g[j]=0;
        while(!g[0]){
            j=i;
            while(g[j]==1){
                g[j]=0;
                j--;
            }
            g[j]=1;
            if(j==0)break;
            aux=1;
            nr=0;
            for(t=j;t;t--)
            if(g[t]==1){
                nr++;
                aux*=div[t];
            }
            if(nr%2)
                total+=a/aux;
            else total-=a/aux;
        }
        fout<<a-total<<"\n";
    }
}