#include<cstdio>
#include<vector>
#include<bitset>
#define LLI long long int
using namespace std;
bitset<500005> BS;
vector<int> P;
int M;
long long F[55];
void precalculare()
{
    int i,j,k;
    P.push_back(2);
    for(i=1; i<500000; i++)
        if(!BS[i])
        {
            k=2*i+1;
            P.push_back(k);
            if(1LL*i*(k+1)<500000) for(j=(i*(k+1)); j<500000; j+=k) BS[j]=1;
        }
}
LLI query(LLI A,LLI B)
{
    vector<int>::iterator it;
    int n=0;
    // descompunere
    for(it=P.begin(); it!=P.end(); it++)
    {
        if(B%(*it)) continue;
        B/=(*it);
        F[++n]=*it;
    }
    if(B>1000000) F[++n]=*it;

    // calcul
    int K=1<<n,i,j,ok;
    long long S=0,p;
    for(i=1; i<K; i++)
    {
        ok=-1;
        p=1;
        for(j=1; j<=n; j++)
            if((1<<(j-1))&i)
            {
                ok*=(-1);
                p*=1LL*F[j];
            }
        S+=ok*A/p;
    }
    return (A-S);
}
int main()
{
    LLI A,B;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&M);
    precalculare();
    for(; M; --M)
    {
        scanf("%lld%lld",&A,&B);
        printf("%lld\n",query(A,B));
    }
    return 0;
}