#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define zs 1000000
#define ll long long
#define pb push_back
ll t, n ,m, nr;
bitset<1000005> b;
vector<ll> v, divz;
void calc_v()
{
    for(int i = 2; i <= zs; ++i)
    {
        if(b[i])continue;
        for(int j = i + i; j <= zs; j += i)
            b[j] = 1;
        v.pb(i);
    }
}
int main()
{
    fin >> t;
    calc_v();
    while(t--)
    {
        fin >> n >> m;
        for(auto i : v)
        {
            if(1LL * i * i > m)break;
            if(m % i == 0)
            {
                divz.pb(i);
                while(m % i == 0)m /= i;
            }
        }
        if(m > 1)divz.pb(m);

        nr = 0;
        for(ll i = 1, prod; i < (1 << divz.size()); ++i)
        {
            int cnt = 0; prod = 1;
            for(int j = 0; j < divz.size(); ++j)
                if(i & (1 << j))
                    prod = 1LL * prod * divz[j], cnt++;
            if(cnt % 2)
                nr += (n /prod);
            else nr -= (n / prod);
        }

        fout << n - nr << '\n';


        divz.clear();
    }
    return 0;
}