#include <fstream>
#define max_val 1000000
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
bool notprim[max_val+100];
int prim[max_val];
int fact[100];
void precalc()
{
    for(int i=2; i<max_val; ++i)
        if(notprim[i]==0)
        {
            prim[++prim[0]]=i;
            for(int j=i*2; j<max_val; j+=i)
                notprim[j]=1;
        }
}

void pinex(int a, int b)
{
    fact[0]=0;
    for(int d=2; d<=b; ++d)
        if(b%d==0)
        {
        fact[++fact[0]]=d;
        while(b && b%d==0)
            b/=d;
        }
    if(b>1)
        fact[++fact[0]]=b;
    int t=fact[0];
    long long prod=0, ans=0, nr=0;
    for(int i=1; i<(1<<t); ++i)
    {
        prod=1; nr=0;
        for(int j=0; j<t; ++j)
            if(((1<<j)&i))
                prod=prod*fact[j+1], ++nr;
        if(nr%2==0)
            nr=-1;
        else nr=1;
        ans=ans+nr*(a/prod);
    }
    cout<<a-ans<<'\n';
}

int main()
{
    int T,A,B;
    precalc();
    cin>>T;
    for(int I=1; I<=T; ++I)
    {
        cin>>A>>B;
        pinex(A,B);
    }
    return 0;
}