#include <fstream>
#include <cmath>
#define MAX 1000000

using namespace std;

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

long long A,B,Rez;
long long Div[1000];
bool Prim[MAX];
int N_Prim[MAX],np;

void ciur()
{
    int i,j;
    N_Prim[++np]=2;
    for(i=3;i*i<=MAX;i+=2)
    {
        N_Prim[++np]=i;
        if(!Prim[i])
            for(j=i*i;j<=MAX;j+=i)
                Prim[j]=1;
    }
}

void calculeaza()
{
    long long i=0;
    int k=0,nr_elem,j;
    long double Sqr = sqrt(B);
    while(B>1)//il descompun pe B in factori primi
    {
        i++;
        while(B%N_Prim[i]==0)
        {
            Div[++k]=N_Prim[i];
            while(B%N_Prim[i]==0)
                B/=N_Prim[i];
        }
        if(B>1&&N_Prim[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;
    ciur();
    while(M--)
    {
        in>>A>>B;
        calculeaza();
        out<<A-Rez<<'\n';
    }
    return 0;
}