#include <iostream>
#include <fstream>

using namespace std;
long long m,a,b;
char viz[1000000];

void ciur(){
    int i,j;
    for(i=2;i<1000000;i++){
        for(j=i+i;j<1000000;j=j+i){
            viz[j]='1';
        }
    }
}

int main()
{
    long long i,j;
    ifstream f("pinex.in");
    ofstream g("pinex.out");
    f>>m;
    ciur();
    //cout<<viz[4];
    int nr=0;
    long long sum1=0;
    long d[4];
    for(i=0;i<m;i++){
        f>>a>>b;
        sum1=0;
        nr=0;
        for(j=2;j<=b;j++){
            if(viz[j]!='1'){
               // if(j>1000000)
                //cout<<j<<'\n';
                if(b%j==0){
                    //cout<<j<<" ";
                    sum1=sum1+a/j;
                    nr++;
                    d[nr]=j;
                }
            }
        }
        if(nr==2){
            sum1=sum1-(a/(d[1]*d[2]));
        }
        if(nr==3){
            sum1=sum1-(a/(d[1]*d[2]))-(a/(d[1]*d[3]))-(a/(d[2]*d[3]))+(a/(d[1]*d[2]*d[3]));
        }
        g<<a-sum1<<'\n';
    }
    return 0;
}