#include <bits/stdc++.h>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
char ciur[1000001];
vector<int> prime;
vector<long long> factp(long long b)
{
    vector<long long> ans;
    for(int i=0;i<prime.size() && 1LL*prime[i]*prime[i]<=b;i++)
    {
        if(b%prime[i]==0)
        {
            ans.push_back(prime[i]);
            while(b%prime[i]==0)
            {
                b=b/prime[i];
            }
        }
    }
    if(b>1) ans.push_back(b);
    return ans;
}
void solve()
{
    long long a,b,ans=0;
    fin>>a>>b;
    vector<long long> fact=factp(b);
    int sz=fact.size();
    for(int mask=0;mask<(1<<sz);mask++)
    {
        int p=0;
        long long nr=1;
        for(int i=0;i<sz;i++)
        {
            if(mask & (1<<i))
            {
                p++;
                nr=1LL*nr*fact[i];
            }
        }
        if(p%2==0)
        {
            ans+=a/nr;
        }
        else
        {
            ans-=a/nr;
        }
    }
    fout<<ans<<'\n';
    return;
}
int main()
{
    for(int i=2;i<1000001;i++)
    {
        if(ciur[i]==0)
        {
            for(int j=i*2;j<1000001;j+=i)
            {
                ciur[j]=1;
            }
            prime.push_back(i);
        }
    }
    ciur[1]=1;
    ciur[0]=1;
    int m;
    fin>>m;
    for(int i=0;i<m;i++)
    {
        solve();
    }
    return 0;
}