#include <fstream>
#include <vector>

using namespace std;

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

int t;
long long a, b;
vector < long long > P;
vector < bool > F(1000010);

int main()
{
    P.push_back(2);
    for (int i = 2; i <= 1000000; i += 2) F[i] = true;
    for (int i = 3; i <= 1000000; i += 2)
    {
        if (!F[i])
        {
            P.push_back(i);
            for (int j = i * i; j <= 1000000; j += i)
            {
                F[j] = true;
            }
        }
    }

    fin >> t;

    while (t --)
    {
        fin >> a >> b;

        vector < int > Div;

        for (vector < long long > :: iterator it = P.begin(); it != P.end() && *it * *it <= b; it ++)
        {
            if (b % *it == 0)
            {
                while (b % *it == 0)
                {
                    b /= *it;
                }
                Div.push_back(*it);
            }
        }

        if (b > 1)
        {
            Div.push_back(b);
        }

        long long sol = 0;
        for (int i = 1; i < (1 << Div.size()); i ++)
        {
            int semn = 0, prod = 1;
            for (int j = 0; j < Div.size(); j ++)
            {
                if (i & (1 << j))
                {
                    prod *= Div[j];
                    semn ++;
                }
            }

            if (semn & 1)
            {
                sol += a / prod;
            }
            else
            {
                sol -= a / prod;
            }
        }

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

    fout.close();
    return 0;
}