#include <fstream>
#include <bitset>
using namespace std;
long long D[60],sir[100000];
bitset <1000005> ciur;
int main()
{
    int cate=0;
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    for(int i=3;i*i<=1000000;i+=2)
        if(ciur[i]==0)
        {
            for(int j=i*i;j<=1000000;j+=i)
                ciur[j]=1;
        }
    sir[++cate]=2;
    for(int i=3;i<=1000000;i+=2)
        for(int j=ciur[i];j<1;j++)
            sir[++cate]=i;
    int T;
    long long a,b;
    cin>>T;
    for(int t=1;t<=T;t++)
    {
        cin>>a>>b;
        long long d=1,ok=0,cnt=0;
        while(sir[d]*sir[d]<=b)
        {
            while(b%sir[d]==0)
            {
                b/=sir[d];
                ok=1;
            }
            if(ok==1)
                D[cnt++]=sir[d];
            ok=0;
            d++;
        }
        if(b>1)
            D[cnt++]=b;
        long long rez=0;
        for(int i=0;i<(1<<cnt);i++)
        {
            long long p=1,nr=0;
            for(int j=0;j<cnt;j++)
            {
                if(i&(1<<j))
                {
                    nr++;
                    p*=D[j];
                }
            }
            if(nr%2==0)
                rez+=a/p;
            else
                rez-=a/p;
        }
        for(int j=0;j<cnt;j++)
            D[j]=0;
        cout<<rez<<"\n";
    }
    return 0;
}