#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
void solve();

bool ciur[1000005];
vector<long long> prime;
long long A, B;

int main()
{
    for(int i = 2; i <= 1000000; ++i)
    {
        if(!ciur[i])
        {
            prime.push_back(i);
            for(int j = i * 2; j <= 1000000; j += i)
                ciur[j] = 1;
        }
    }

    int m;
    fin>>m;
    while(m--)
        solve();

    return 0;
}

void solve()
{
    vector<long long> diviz;
    fin>>A>>B;

    for(auto d : prime)
    {
        if(B % d == 0)
        {
            diviz.push_back(d);
            B /= d;
        }
    }
    if(B != 1)
        diviz.push_back(B);

    long long ans = 0, tot = (1<<diviz.size()) - 1;
    for(long long mask = 1; mask <= tot; ++mask)
    {
        long long semn, d = 1;

        if(__builtin_popcount(mask) % 2 == 0)
            semn = -1;
        else
            semn = 1;

        for(long long i = 0; (1<<i) <= mask; ++i)
        {
            if((1<<i) & mask)
                d = d * diviz[i];
        }
        ans += semn * A / d;
    }
    fout<<A - ans<<"\n";
}