#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;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnR5cGVkZWYgbG9uZyBsb25nIGxsOwp1c2luZyBuYW1lc3BhY2Ugc3RkOwp2b2lkIENvZGVfQnlfTW9oYW1lZF9LaGFsZWQoKSB7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUobnVsbHB0cik7CiAgICBjb3V0LnRpZShudWxscHRyKTsKLy8gI2lmbmRlZiBPTkxJTkVfSlVER0UKLy8gICAgIGZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pOwovLyAgICAgZnJlb3Blbigib3V0cHV0LnR4dCIsICJ3Iiwgc3Rkb3V0KTsKLy8gI2VuZGlmCn0KaW50IG1haW4oKSB7CiAgICBDb2RlX0J5X01vaGFtZWRfS2hhbGVkKCk7CiAgICBsbCB0O2Npbj4+dDsKICAgIHdoaWxlICh0LS0pIHsKICAgICAgICBsbCBuLGs7Y2luPj5uPj5rO2xsIGFucz0wOwogICAgICAgIGZvciAobGwgaT0xO2kqaTw9aztpKyspIHsKICAgICAgICAgICAgaWYgKGslaT09MCkgewogICAgICAgICAgICAgICAgbGwgaj1rL2k7CiAgICAgICAgICAgICAgICBpZiAoX19nY2QoaSxqKT09MSkgewogICAgICAgICAgICAgICAgICAgIGlmIChpIT1qKWFucys9Mioobi8obWF4KGksaikpKTsKICAgICAgICAgICAgICAgICAgICBlbHNlIGFucys9bi9tYXgoaSxqKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBjb3V0PDxhbnM8PCJcbiI7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==

MjAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAKMTAwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMDAK

20
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000
10000000000000 10000000000000