#include <fstream>
#include <iostream>

using namespace std;
ifstream fin ("pinex.in");
ofstream fout ("pinex.out");
const int VAL_MAX=1000000;
int m, a, b, prime[10000], cnt_prime;
int ciur[VAL_MAX+5], div_primi_b[10000], cnt_div_b;
void gen_prime ()
{
    prime[++cnt_prime]=2;
    for(int i=3; i<=VAL_MAX; i+=2)
    {
        if(!ciur[i])
        {
            prime[++cnt_prime]=i;
            for(int j=2*i; j<=VAL_MAX; j+=i)
                ciur[j]=1;
        }
    }
}
void find_div_primi_b ()
{
    for(int i=0; i<=10000; i++)
        div_primi_b[i]=0;
    cnt_div_b=0;
    int cb=b, i=1;
    while(cb>1)
    {
        if(cb%prime[i]==0) div_primi_b[++cnt_div_b]=prime[i];
        while(cb%prime[i]==0)
            cb/=prime[i];
        i++;
    }
}

int calcul_neprime_cu_b ()
{
    int neprime_cu_b=0;
    long long lim=(1<<cnt_div_b);
    for(int i=1; i<lim; i++)
    {
        int prod_div=1, cnt=0;
        for(int j=0; j<cnt_div_b; j++)
            if(i&(1<<j))
            {
                prod_div*=div_primi_b[j+1];
                cnt++;
            }
        int val=a/prod_div;
        if(cnt%2==0)
            val*=(-1);
        neprime_cu_b+=val;
    }
    return neprime_cu_b;
}
int main()
{
    fin>>m;
    gen_prime();
    for(int k=1; k<=m; k++)
    {
        fin>>a>>b;
        find_div_primi_b();
        /*for(int i=1; i<=cnt_div_b; i++)
            cout<<div_primi_b[i]<<" ";
        cout<<"\n";*/
        fout<<a-calcul_neprime_cu_b()<<"\n";
    }
    return 0;
}