#include <fstream>
#include <vector>

using namespace std;
using ll = long long;

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

vector <ll> v;
int main()
{
    int t;
    cin >> t;
    while(t--) {
        v.clear();
        ll a, b; ///cate nr <=a prime cu b - dar noi facem nr NEPRIME cu b
        cin >> a >> b;
        ll d = 2;
        while(d * d <= b) {
            int exp = 0;
            while(b % d == 0) {
                exp++;
                b /= d;
            }
            if(exp > 0)
                v.push_back(d);
            d++;
        }
        if(b > 1)
            v.push_back(b);
        /*for(auto var : v)
            cout << var << " ";*/
        int n = v.size();
        ll ans = 0;
        for(int mask = 0; mask < (1 << n); mask++) {
            if(mask == 0)
                continue;
            int nrbiti = 0;
            ll card = 1; ///nr respectiv format din cardinal
            for(int i = 0; i < n; i++) {
                if(mask & (1 << i)) {
                    nrbiti++;
                    card *= v[i];
                }
            }
            if(nrbiti % 2 == 1)
                ans += (a / card);
            else
                ans -= (a / card);
        }
        cout << a - ans << '\n';
    }
    return 0;
}