#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

#define cin fin
#define cout fout

bitset <1000004> ciur;
int prime[1000004],v[1000004],a,b,nr,n;

void ciurulet()
{
    ciur[0]=ciur[1]=1;
    for(long long i = 2; i < 1000004; i++)
    {
        if(ciur[i] == 0)
        {
            prime[++prime[0]] = i;
            for(long long j = i * i; j < 1000004; j += i) ciur[j]=1;
        }
    }
}

void qwe(int a, int b)
{
    v[0]=0; int nr=0;
    for(int i=1;i<= prime[0];i++)
    {
        if(b%prime[i]==0)
        {
            v[++v[0]]=prime[i];
        }
        while(b%prime[i]==0) b/=prime[i];
        if(b==1) i=prime[0]+1;
    }
    if(b>1) v[++v[0]]=b;
    for(int i=1;i<(1 << v[0]);i++)
    {
        int nrbiti=0; int val=1;
        for(int j = 0; (1 << j) <= i; ++j)
        {
            if((1 << j) & i)
            {
                ++nrbiti;
                val *= v[j + 1];
            }
        }
        if(nrbiti & 1) nrbiti = 1;
        else nrbiti = -1;
        nr = nr+nrbiti*a/val;
    }
    cout<<a-nr<<"\n";
    for(int i=1;i<=v[0];i++) v[i]=0;
}

int main()
{
    cin>>n;
    ciurulet();
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;
        qwe(a,b);
    }
    return 0;
}