#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long m, A, B, ciur[1000005], prime[80000], nrprime, divprimi[20], nrdivprimi, sol;
void bcktrck(long long ind, long long divizor, long long num, long long a)
{
    if(ind==nrdivprimi)
    {
        if(num>0)
        {
            if(num%2==1)
                sol-=a/divizor;
            else
                sol+=a/divizor;
        }
    }
    else
    {
        bcktrck(ind+1, divizor, num, a);
        bcktrck(ind+1, divizor*divprimi[ind+1], num+1, a);
    }
}
void ciurr()
{
    for(int i=2; i*i<=1000000; i++)
        if(ciur[i]==0)
            for(int j=i*i; j<=1000000; j+=i)
                ciur[j]=1;
    for(int i=2; i<=1000000; i++)
        if(ciur[i]==0)
            prime[++nrprime]=i;
}
void query(long long a, long long b)
{
    nrdivprimi=0;
    sol=a;
    for(int i=1; i<=nrprime; i++)
    {
        if(b%prime[i]==0)
        {
            divprimi[++nrdivprimi]=prime[i];
            while(b%prime[i]==0)
                b/=prime[i];
        }
    }
    if(b>1)
        divprimi[++nrdivprimi]=b;
    bcktrck(0, 1, 0, a);
    fout << sol << "\n";
}
int main()
{
    ciurr();
    fin >> m;
    for(int i=1; i<=m; i++)
    {
        fin >> A >> B;
        query(A, B);
    }
    return 0;
}