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

using namespace std;
long long prime[20], suma, primelePrime[10000];
char ciur[MAX + 1];

void precalculare()
{
    int i, j, k = 1;

    for(i = 2; i * i <= MAX; i++)
        if(ciur[i] == 0)
        {
            primelePrime[k] = i;
            k++;
         //   cout << k << " ";
            for(j = i * i; j <= MAX; j += i){
            //    cout << j << " ";
                ciur[j] = 1;
            }
        }
}

int rezolvare(long long a, long long  i, long long n, long long contor, long long k, long long subFractie){
    int j;

    if(k <= contor)
        for(j = i + 1; j <= n; j++)
        {
            rezolvare(a, j, n, contor, k + 1, subFractie * prime[j]);
        }
    else{
        if(contor % 2 == 0)suma = suma - a / subFractie;
       else  suma = suma + a / subFractie;
    }
}

int main()
{
    long long m, a, b, i, j, contor, n, k;

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

    precalculare();

    fin >> m;

    for(i = 1; i <= m; i++)
    {
        fin >> a >> b;

        contor = 1;
        j = 1;
        while(primelePrime[contor] * primelePrime[contor] <= b)
        {
            if(b % primelePrime[contor] == 0)
            {
                prime[j] = primelePrime[contor];
                j++;
                while(b % primelePrime[contor] == 0)b /= primelePrime[contor];
            }

            contor++;
        }

        if(b > 1)
        {
            prime[j] = b;
            j++;
        }

        suma = 0;
        n = j - 1;
        for(j = 1; j <= n; j++){
            rezolvare(a, 0, n, j, 1, 1);
            //cout << suma << ' ';
        }

        fout << a - suma << '\n';
    }

    fin.close();
    fout.close();

    return 0;
}