#include <fstream>
#include <vector>
#include <utility>
#include <bitset>
#define int long long
using namespace std;
ifstream fcin("pinex.in");
ofstream fout("pinex.out");
int q,a,b;
bitset <2000005> c;
vector <int> m, prime;
inline int cmmmc(int a, int b)
{
    int p=a*b;
    while(b!=0)
    {
        int r=a%b;
        a=b;
        b=r;
    }
    return p/a;
}
inline int solve(int x, int y)
{
    m.clear();
    int rez=0;
    for(int i=0; prime[i]*prime[i]<=y; i++)
    {
        int d=prime[i];
        int e=0;
        while(y%d==0) y=y/d, e++;
        if(e) m.push_back(d);
    }
    if(y>1) m.push_back(y);
    int n=(1<<m.size());
    for(int i=1; i<n; i++)
    {
        int nr=0;
        int val;
        for(int j=0; j<m.size(); j++)
        {
            if((((1<<j) & i) ^ 0))
            {
                nr++;
                if(nr==1) val=m[j];
                else val=cmmmc(val,m[j]);
            }
        }
        if((nr & 1)) rez+=(x/val);
        else rez-=(x/val);
    }
    return x-rez;
}
signed main()
{
    for(int i=2; i<=1e6+5; i++)
    {
        if(c[i]==0)
        {
            prime.push_back(i);
            for(int j=2*i; j<=1e6+5; j+=i)
                 c[j]=1;
        }
    }
    fcin>>q;
    while(q--)
    {
        fcin>>a>>b;
        fout<<solve(a,b)<<'\n';
    }
    return 0;
}