#include <fstream>
#include <cmath>

using namespace std;

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

long long A,B,Rez;
long long Div[1000];

void calculeaza()
{
    long long i=1;
    int k=0,nr_elem,j;
    long double Sqr = sqrt(B);
    while(B>1)//il descompun pe B in factori primi
    {
        i++;
        while(B%i==0)
        {
            Div[++k]=i;
            while(B%i==0)
                B/=i;
        }
        if(B>1&&i>Sqr)
            Div[++k]=B,B=1;
    }
    Rez=0;
    long long nr_comb = (1<<k)-1,produs;
    for(i=1;i<=nr_comb;i++)
    {
        produs = 1,nr_elem=0;
        for(j=0;j<k;j++)
            if(i&(1<<j))//bitul j e true
                produs*=Div[j+1],nr_elem++;
        if(nr_elem&1)//impar
            Rez+=A/produs;
        else Rez-=A/produs;
    }
}

int main()
{
    int M;
    in>>M;
    while(M--)
    {
        in>>A>>B;
        calculeaza();
        out<<A-Rez<<'\n';
    }
    return 0;
}