#include<bits/stdc++.h>
using namespace std;
int zd(int a,int b){   //最大公约数
	if(b==0){
			 return a;
	}
	return zd(b,a%b);
}
int main(){
	int t;
	cin>>t;
	while(t--){
		long long sum=0;
		int n,x;
		cin>>n>>x;
		for(int i=1;i*i<=x;i++){
			if(x%i==0){
				int a=i;
				int b=x/i;
//				cout<<a<<' '<<b<<endl;
				if(zd(a,b)==1){
					sum+=n/b;
					if(a!=b){
						sum+=n/b;
					}
					continue;
				}
			}
//			cout<<endl<<endl;
		}
		cout<<sum<<"\n";
	}
	return 0;
}