#include <fstream>
#include<vector>
using namespace std;

#define ll long long 

ifstream cin("pinex.in");
ofstream cout("pinex.out");

vector<ll> v;

int main()
{
    ll i, j, nr,t,a,b, n;

    cin >> t;
    
    while (t > 0) {
        cin >> a >> b;

        ll d = 2, len = 0, res = 0;

        while (b > 1) {
            if (b % d == 0) {
                v.push_back(d);
                len++;
                res += a / d;
                while (b % d == 0) {
                    b /= d;
                }
            }
            if (d * d > b) {
                if (b == 1)
                    break;
                v.push_back(b);
                len++;
                res += a / b;
                b = 1;
            }
            else {
                d++;
            }
        }

        ll pw = ((ll)1 << len);
        ll nr;
        if (len > 2) {
            pw--;
        }
        for (nr = 1; nr < pw; nr++) {
            ll pt = 1, cnt = 0;
            for (i = 0; i < len; i++) {
                if (nr & (1 << i)) {
                    pt *= v[i];
                    cnt++;
                }
            }
            if (cnt > 1)
                res -= a / pt;
        }

        if (len > 2) {
            ll pt = 1, cnt = 0;
            for (i = 0; i < len; i++) {
                if (nr & (1 << i)) {
                    pt *= v[i];
                }
            }
            res += a / pt;
        }

        cout << a - res << "\n";

        v.clear();
        t--;
    }
    return 0;
}