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

ifstream cin("pinex.in");
ofstream cout("pinex.out");

long long  t,a,b,nrf;
long long pr[1000000],fact[20];
bool prime[1000320];

void ciur()
{
    long long i,j;
    for (i=1;i<=1000000;i++) prime[i]=true;
    long long  nrpr=0;
    for (i=2;i<=1000000;i++)
    if (prime[i]) {
        pr[++nrpr]=i;
        for (j=i*i;j<=1000000;j+=i)
            prime[j]=false;
    }
}
void factori() {
    nrf=0; int i=1;
    while (b>1) {
        if (b%pr[i]==0) {
            fact[++nrf]=pr[i];
            while (b%pr[i]==0) b/=pr[i];
        }
        i++;
        if (pr[i]*pr[i]>b && b>1)
            fact[++nrf]=b, b=1;
    }
}

void solve() {
    factori();
    long long  i,j,r=0,nr=0;
    for (i=1;i<=(1<<nrf);i++) {
        long long nr=0, f=1;
        for (j=0;j<nrf;j++)
            if (i&(1<<j)) nr++,
                f*=fact[j+1];
        if (nr)
        r+=(nr%2)? (a/f) : -(a/f);
    }
    cout<<a-r<<"\n";
}

int main()
{
    cin>>t;
    ciur();
    for (;t--;) {
        cin>>a>>b;
        solve();
    }
    return 0;
}