#include <bits/stdc++.h>
#define NM 1000005
#define ll long long
using namespace std;
ifstream fin ("pinex.in");
ofstream fout ("pinex.out");
bitset<NM> c;
vector<int> prime;
void ciur()
{
    c[0] = c[1] = 1;
    for(int i=4; i<NM; i+=2)
        c[i] = 1;
    for(int i=3; i*i<NM; i+=2)
        if(!c[i])
            for(int j=i*i; j<NM; j+=2*i)
                c[j] = 1;
    prime.push_back(2);
    for(int i=3; i<NM; i+=2)
        if(!c[i])
            prime.push_back(i);
}
void solve(ll a, ll b)
{
    vector<int> v;///prime factors of b
    ll k = 0, rez = 0;
    while(prime[k]*prime[k]<=b)
    {
        if(b%prime[k] == 0)
        {
            v.push_back(prime[k]);
            while(b%prime[k] == 0)
                b/=prime[k];
        }
        ++k;
    }
    if(b > 1)
        v.push_back(b);
    ll maxim = (1<<v.size())-1;
    for(ll i=1; i<=maxim; ++i)
    {
        ll prod = 1, nr = 0;
        for(int j=0; j<v.size(); ++j)
            if(i&(1LL<<j))
            {
                prod*=v[j];
                nr++;
            }
        if(nr%2==1)
            rez+=a/prod;
        else
            rez-=a/prod;
    }
    fout << a-rez << '\n';
}
int main()
{
    ciur();
    ll q, A, B;
    fin >> q;
    for(int i=1; i<=q; i++)
    {
        fin >> A >> B;
        solve(A, B);
    }
    return 0;
}