#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void Code_By_Mohamed_Khaled() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
}
int main() {
    Code_By_Mohamed_Khaled();
    ll t;cin>>t;
    while (t--) {
        ll n,k;cin>>n>>k;ll ans=0;
        for (ll i=1;i*i<=k;i++) {
            if (k%i==0) {
                ll j=k/i;
                if (__gcd(i,j)==1) {
                    if (i!=j)ans+=2*(n/(max(i,j)));
                    else ans+=n/max(i,j);
                }
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}