#include<iostream>
#include<fstream>

using namespace std;

const int Bsqrt = 1e6 + 5;
ifstream f("pinex.in");
ofstream g("pinex.out");

long long ciur[Bsqrt];

void ciur1()
{
    for(int i=1;i<Bsqrt;i++)
        ciur[i] = 0;
    for(int i=2;i*i<Bsqrt;i++)
    {
        if(ciur[i] == 0)
            for(int j=i;j<Bsqrt;j=j+i)
                ciur[j]++;
    }
}

long long query(long long a,long long b)
{
    long long ans = 0;
    if(ciur[b] % 2 == 1)
        ans = ans + a/b;
    else
        ans = ans - a/b;
    for(int i=2;i*i<=b;i++)
    {
        if(b%i == 0)
        {
            if(ciur[i] % 2 == 1)
                ans = ans + a/i;
            else
                ans = ans - a/i;
            if(ciur[b/i] % 2 == 1)
                ans = ans + a/(b/i);
            else
                ans = ans - a/(b/i);
        }
    }
    return a-ans;
}

int main()
{
    ciur1();
    int t;
    f>>t;
    while(t--)
    {
        long long a,b;
        f>>a>>b;
        g<<query(a,b)<<"\n";
    }
}