#include <iostream>
#include<fstream>
#include<vector>
using namespace std;ifstream fin("pinex.in");ofstream fout("pinex.out");
int m,erat[1000001],i,j,cnt,k,nr;long long a,b,p,rez,cp;bool ok;vector<int>prim,v;vector<int>::iterator it;
int main()
{
    for(i=2;i<=1e6;i++)if(!erat[i]){
            prim.push_back(i);
        for(j=i*2;j<=1e6;j+=i)erat[j]=1;
    }
    fin>>m;while(m--){rez=0;
        fin>>a>>b;v.clear();
        for(it=prim.begin();b>1;it++){
            ok=0;while(b%*it==0){ok=1;b/=*it;}
            if(ok)v.push_back(*it);
            if(*it**it>b){v.push_back(b);break;}
        }k=v.size();
        for(i=1;i<(1<<k);i++){
            cnt=0;p=1;for(j=0;j<k;j++)if(i&(1<<j)){nr=0;
            cp=p;while(cp){nr++;cp/=10;}cp=v[j];while(cp){nr++;cp/=10;}if(nr>18){p=1e19;break;}
            p*=v[j];if(p>a)break;cnt++;}
            if(cnt&1)rez+=a/p;
            else rez-=a/p;
        }fout<<a-rez<<'\n';
    }
    return 0;
}