#include <bits/stdc++.h>

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