///circular
//unordered_
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int i,j,y,n,m,a,b,k,nr,s,v[1010];
long long p;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    fin>>m;
    for(y=1; y<=m; y++)
    {
        fin>>a>>b;
        if(b%2==0)
            v[++k]=2;
        while(b%2==0)
            b/=2;
        j=3;
        while(b>1)
        {
            if(b%j==0)
                v[++k]=j;
            while(b%j==0)
                b/=j;
            j+=2;
        }
        for(i=1; i<(1<<k); i++)
        {
            p=1;
            nr=__builtin_popcount(i);
            for(j=1; j<=k; j++)
                if((i&(1<<(j-1)))!=0)
                    p*=v[j];
            if(nr%2==1)
                s+=a/p;
            else
                s-=a/p;
        }
        fout<<a-s<<'\n';
        s=0;
        k=0;
    }
    return 0;
}