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

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

vector<int>primi;

long long n, a, b, divizori[100000],k,aux,lungime,suma,variabila;
bool ciur[1000005],viz[1000000];

void ciur_erath()
{
    ciur[0]=1;
    ciur[1]=1;
    for (int i=2; i<=1000000; i++)
    {
        if (ciur[i]==0)
        {
            primi.push_back(i);
            aux=i*2;
            while (aux<1000000)
                ciur[aux]=1,aux+=i;
        }
    }
}

int formdiv(int b)
{
    for (int i=0; i<lungime; i++)
    {
        if (primi[i]*primi[i]>b)
            break;
        if (b%primi[i]==0)
        {
            divizori[k++]=primi[i];
            while (b%primi[i]==0)
            {
                b/=primi[i];
            }
        }
    }
    if (b>1)
    {
        divizori[k++]=b;
    }

}

void backt(int lvl,int ant)
{
    if (lvl==n+1)
        return;
    if (ant==k-1)
        return;
    for (int i=ant+1; i<k; i++)
    {
        variabila*=divizori[i];
        backt(lvl+1,i);
        if (lvl%2==0)
            suma-=(a/variabila);
        else
            suma+=(a/variabila);
        variabila/=primi[i];
    }
}

int main()
{
    f >> n;
    ciur_erath();
    lungime=primi.size();
    for (int i=1; i<=n; i++)
    {
        suma=0;
        memset(divizori,0,k);
        k=0;
        f >> a >> b;
        variabila=1;
        formdiv(b);
        backt(1,-1);
        g << a-suma << '\n';

    }
    return 0;
}