#include <fstream>
#include <vector>
#include <bitset>
using namespace std;

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

int prime[78499];

vector <long long> Descompunere (long long numar)
{
    vector <long long> factori;
    for (int indice = 1 ; indice <= prime[0] && 1LL * prime[indice] * prime[indice] <= numar ; indice++)
        if (numar % prime[indice] == 0)
        {
            factori.push_back(prime[indice]);
            while (numar % prime[indice] == 0)
                numar /= prime[indice];
        }

    if (numar > 1)
        factori.push_back(numar);

    return factori;
}

long long Query (long long lungime , vector <long long> factori)
{
    long long rezultat = 0;
    for (int masca = 1 , limita = (1 << factori.size()) - 1 ; masca <= limita ; masca++)
    {
        long long factor = 1 , semn = -1;
        for (int indice = 0 , putere = 1 ; putere <= masca ; indice++ , putere <<= 1)
            if (masca & putere) { factor *= factori[indice]; semn *= -1; }

        rezultat += lungime / factor * semn;
    }
    
    return rezultat;
}

int main ()
{
    prime[++prime[0]] = 2;
    bitset <500000> compus;
    for (int valoare = 3 ; valoare < 1e6 ; valoare += 2)
        if (!compus[(valoare - 1) >> 1])
        {
            prime[++prime[0]] = valoare;
            for (long long multiplu = 1LL * valoare * valoare ; multiplu < 1e6 ; multiplu += (valoare << 1))
                compus[(multiplu - 1) >> 1] = 1;
        }

    int intrebari;
    cin >> intrebari;

    long long limita , numar;
    for (int indice = 1 ; indice <= intrebari ; indice++) 
        { cin >> limita >> numar; cout << limita - Query(limita , Descompunere(numar)) << '\n'; }

    cout.close(); cin.close();
    return 0;
}