#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define LL __int64#define N 100002using namespace std;bool isprime[N];LL prime[N],np;LL fac[100],fp;void initial(){	memset(isprime,true,sizeof(isprime));	np=0;	for(LL i=2;i<N;i++){		if(isprime[i]){			prime[np++]=i;			for(LL j=i*i;j<N;j+=i)			isprime[j]=false;		}	}}void dfs(LL i,LL num,LL p,LL &ans,LL s,LL &n){	if(i>=s){		if(num==0)		ans=n;		else if(num&1)		ans-=(n/p);		else ans+=(n/p);		return ;	}	dfs(i+1,num,p,ans,s,n);	dfs(i+1,num+1,p*fac[i],ans,s,n);}LL work(LL m,LL n){	fp=0; 	for(LL i=0;i<np&&prime[i]*prime[i]<=m;i++){	 	if(m%prime[i]==0){	 		while(m%prime[i]==0){	 			m/=prime[i];	 		}	 		fac[fp++]=prime[i];	 	} 	} 	if(m>1) fac[fp++]=m; 	 	LL ans; 	dfs(0,0,1,ans,fp,n); 	return ans; 	}int main(){	int T;	initial();	scanf("%d",&T);	while(T--){		LL m,n;		scanf("%I64d%I64d",&m,&n);		LL ans=n;		for(LL i=2;i<=m;i++)			ans+=work(i,n);		printf("%I64d\n",ans);	}	return 0;}