#include <fstream>
#include <vector>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");

vector <int> v,p;

int prim(int n)
{
    for(int i=3;i*i<=n;i+=2)
        if(n%i==0)
            return 0;
    return 1;
}

void f()
{
    p.push_back(2);
    for(int i=3;i<=1000000;i+=2)
        if(prim(i)==1)
            p.push_back(i);
}

long long neprime(long long a,long long b)
{
    int i=1;
    long long rez=0;
    while(b!=1&&p[i]<=a)
    {
        if(b%p[i]==0)
            v.push_back(p[i]);
        while(b%p[i]==0)
            b/=p[i];
        i++;
    }
    int n=v.size();
    for(int i=1;i<(1<<n);i++)
    {
        long long prod=1,nr=0;
        for(int j=0;j<n;j++) //parcurgem vectorul cu divizorii primi ai lui b
            if((1<<j)&i) // verif daca bitul j este marcat in i
            {
                prod=prod*v[j];
                nr++;
            }
        if(nr%2==0)
            rez=rez-a/prod;
        else
            rez=rez+a/prod;
    }
    v.clear();
    return rez;

}

int main()
{
    long long a,b;
    int m;
    cin>>m;
    f();
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        cout<<a-neprime(a,b)<<'\n';
    }
    return 0;
}