#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
vector<int>nrprim,divizors;
bitset<1000001>ap;
int m,lenght,opmax;
unsigned long long a,b;
int bkk(int nr,int op)
{
    if(op==opmax && nr==1)
        return 0;
    if(op==opmax)
        return 1;
    if(nr%divizors[op]==0)
        return 0;
    int p=bkk(nr,op+1);
    for(int i=1;i<=a;i++)
    {
        if(nr*divizors[op]*i>a)
            return p;
        if(nr%i==0 && i>1)
            return p;
            cout<<b<<"\n";
        p+=bkk(nr*divizors[op]*i,op+1);
    }
}
void solve()
{
    divizors.clear();
    long long copb=b;
    for(int i=0;i<lenght;i++)
    {
        if(copb%nrprim[i]!=0)
            continue;
        while(copb%nrprim[i]==0)copb/=nrprim[i];
        divizors.push_back(nrprim[i]);
        if(copb==1)
            break;
    }
    opmax=divizors.size();
    int howmany=bkk(1,0);
    fout<<a-howmany<<"\n";
}
void make_prime()
{
    for(int i=2;i<=1000000;i++)
    {
        if(ap[i])
            continue;
        nrprim.push_back(i);
        int j=2*i;
        while(j<=1000000)
        {
            ap[j]=1;
            j+=i;
        }
    }
    lenght=nrprim.size();
}
int main()
{
    fin>>m;
    make_prime();
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b;
        solve();
    }
    return 0;
}