#include<iostream>
#include<fstream>
using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

bool ciur[1000002];

void ciur1(long long val)
{
    for(int i=1;i<=val;i++)
        ciur[i] = false;
    for(int i=2;i*i<=val;i++)
    {
        if(ciur[i] == false)
            for(int j=i*2;j<=val;j=j+i)
                ciur[j] = true;
    }
}

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

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