#include<bits/stdc++.h>
using namespace std;

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

long long a, b;

long long ans; /// ans = nr de numere neprime cu un numar n
long long d[12]; /// vectorul de divizori numere prime al unui numar n
int nr, s[12]; /// nr = lungimea vectorului d ; s[] = vectorul de solutii

bool ciur[1000001]; /// ciurul lui Eratostene
int nrprim[200000], cnt; /// toate numerele prime pana la 1 milion ; cnt = cate nr prime sunt
// nrprim[1]=2 nrprim[2]=3 ....

void ciurul_lui_eratostene()
{
    ciur[1]=1;
    for(int i=2; i*i<=1000001; i++)
        if(ciur[i]==0)
        {
            for(int j=i; i*j<=1000001; j++)
                ciur[i*j]=1;
        }

    for(int i=2; i<=1000001; i++)
        if(ciur[i]==0)
            nrprim[++cnt]=i;
}

void vector_de_divizori(long long n)
{
    /// construirea vectorului de divizori al unui numar n
    for(int i=1; i<=cnt && nrprim[i]*nrprim[i]<=n; i++)
        if(n%nrprim[i]==0)
        {
            d[++nr]=nrprim[i];

            while(n%nrprim[i]==0)
                n/=nrprim[i];
        }

    if(n>1)
    {
        nr++;
        d[nr]=n;
    }
}

void intersectia_submultimilor(int k, long long a)
{
    long long p=1; /// p = nr format la intersectia (sub)multimilor

    for(int i=1;  i<=k; i++)
        p *= d[s[i]];

    /// a/p = numarul de numere <=a divizibile cu p (produs de divizori ai lui n)
    /// k par - scadem
    /// k impar - adunam

    if(k%2==0)
        ans=ans-a/p;
    else
        ans+=(a/p);
}

void bkt(int k, int l, long long a) ///se construieste vectorul de solutii
{
    /// l = marimea submultimii
    for(int i= s[k-1]+1; i <=nr+k-l; i++)
    {
        s[k]=i;

        if(k==l)
            intersectia_submultimilor(k, a);
        else
            bkt(k+1, l, a);
    }
}

void nr_prime(long long a, long long n)
{
    nr=0;
    vector_de_divizori(n);

    /// aflarea numarului de numere <=a prime cu n;
    ans=0;
    for(int i=1; i<=nr; i++)
        bkt(1, i, a);
}

int main()
{
    ciurul_lui_eratostene();

    int m;
    in >> m;

    for(int i=1; i<=m; i++)
    {
        in >> a >> b;
        //out << nr_prime(a, b) << '\n';

        /*nr=0;
        for(int i=1; i<=cnt && nrprim[i]*nrprim[i]<=b; i++)
            if(b%nrprim[i]==0)
            {
                d[++nr]=nrprim[i];

                while(b%nrprim[i]==0)
                    b/=nrprim[i];
            }

        if(b>1)
        {
            nr++;
            d[nr]=b;
        }

        /// aflarea numarului de numere <=a prime cu n;
        ans=0;
        for(int i=1; i<=nr; i++)
            bkt(1, i, a);*/

        nr_prime(a, b);
        out << a-ans << '\n';
    }



    return 0;
}