#include <fstream>
#include <iostream>

using namespace std;
long long prime[20], suma;

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;

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

    fin >> m;

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

        contor = 2;
        j = 1;
        while(contor * contor <= b)
        {
            if(b % contor == 0)
            {
                prime[j] = contor;
                j++;
                while(b % contor == 0)b /= 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;
}