#include <fstream>
#include <vector>
using namespace std;
const int VMAX = 1e6;
bool c[VMAX];
vector <int> p;
void ciur()
{
    p.push_back(2);
    for (int i = 3; i * i <= VMAX; i += 2)
        if (!c[i])
            for (int j = i * i; j <= VMAX; j += (i << 1))
                c[j] = 1;
    for (int i = 3; i <= VMAX; i += 2)
        if (!c[i])
            p.push_back(i);
}
int main()
{
    ciur();
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    int n;
    cin >> n;
    while (n--)
    {
        vector <int> d;
        long long a, b;
        cin >> a >> b;
        for (int i = 0; i < p.size() and p[i] * p[i] <= b; i++)
            if (b % p[i] == 0)
            {
                while (b % p[i] == 0)
                    b /= p[i];
                d.push_back(p[i]);
            }
        if (b > 1)
            d.push_back(b);
        long long val = 0;
        int dim = (1 << d.size());
        for (int i = 1; i < dim; i++)
        {
            long long prod = 1;
            int cnt = 0;
            for (int j = 0; (1 << j) <= i; j++)
                if (i & (1 << j))
                {
                    cnt++;
                    prod *= d[j];
                }
            if (cnt % 2 == 0)
                val -= a / prod;
            else
                val += a / prod;
        }
        cout << a - val << "\n";
    }
}