#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define ll long long
const int Nmax = 1000000 + 5;
vector <ll > v;
vector <ll > dv;
ll card[Nmax];
#define pb push_back
bitset<Nmax>b;
ll n, m, k, sol, t;
void prim()
{
    for(ll i = 2; i <= 1000000; ++i)
        if(!b[i])
        {
            for(ll j = i; j <= 1000000; j += i)
                b[j] = 1;
            v.pb(i);
        }
}
int main()
{
    prim();
    fin >> t;
    while(t--)
    {
        fin >> n >> m;
        for(auto i : v)
        {
            if(1LL * i * i > m)break;
            ll divz = i;
            if(!(m % divz))
            {
                while(!(m % divz))m/=divz;
                dv.pb(divz);
            }
        }
        if(m > 1)dv.pb(m);
        k = dv.size();
        for(int i = 1, prod, nr; i < (1 << k); ++i)
        {
            prod = 1, nr = 0;
            for(int j = 0; j < k; ++j)
               if(i & (1 << j))
                {
                    prod *= dv[j];
                    nr ++;
                }
            if(nr % 2)
                sol += (n / prod);
            else sol -= (n / prod);
        }
        fout <<n - sol << '\n';
        sol = 0; k = 0; dv.clear();
    }
    return 0;
}