#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");

int m;
long long a, b;
// int div[80003],cnt;

void divizori(vector<int> &v, long long cb)
{
    if (cb % 2 == 0)
    {
        v.push_back(2);
        while (cb % 2 == 0)
            cb /= 2;
    }
    for (int i = 3; i * i <= cb; i += 2)
    {
        if (cb % i == 0)
        {
            v.push_back(i);
            while (cb % i == 0)
            {
                cb /= i;
            }
        }
    }
    if (cb > 1)
        v.push_back(cb);
}

int main()
{
    f >> m;
    for (int i = 1; i <= m; ++i)
    {
        f >> a >> b;
        vector<int> div;
        divizori(div, b);
        long long sumdiv = 0;
        int nr = div.size();
        int sgn = 1;

        // for (int i = 0; i < nr; ++i)
        // {
        //     g << div[i] << ' ';
        // }
        // g << '\n';

        for (int j = 1; j < (1 << nr); ++j)
        {
            int cnt = 0;
            long long x = 1;
            for (int k = 0; k < nr; ++k)
            {
                if (j & (1 << k))
                {
                    cnt++;
                    x *= div[k];
                }
            }
            if (cnt % 2)
                sgn = 1;
            else
                sgn = -1;
            // g << x << ' ' << sgn << '\n';
            sumdiv += sgn * a / x;
        }

        g << a - sumdiv << '\n';
    }
    return 0;
}