#include <fstream>
#include <vector>
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
long long k, i, j, q, a, b, ans;
long long v1[] = {1, -1};
vector<long long> v;
void fnc()
{
    if (j % i == 0)
        v.push_back(i);
    while(j%i == 0)
        j/=i;
}
int main()
{
    in >> q;
    while(q)
    {
        q--;
        ans = 0;
        in >> a >> b;
        v.clear();
        j = b;
        i = 2;
        fnc();
        for (i = 3; i * i <= j; i+=2)
            fnc();
        if (j != 1)
            v.push_back(j);
        k = v.size();
        for (i = 1; i < (1<<k); i++) ///i == mask
        {
            long long nr = 0, p = 1;
            for (j = 0; j < k; j++)
                if ((i & (1 << (j)))!=0)
                {
                    p *= v[j];
                    nr++;
                }
            ans += a/p * v1[1-nr%2];
        }
        out << a - ans << '\n';

    }
    return 0;
}