#include "bits/stdc++.h"

#define endl '\n'
#define SZ(v) int((v).size())
using namespace std;
typedef long long ll;
const int N = 1e5 + 7, M = 2 * N;
using vi = vector<int>;

int comp[N + 1];
vi primes;
void sieve() {
    for (int i = 2; i <= N; ++i) {
        int &x = comp[i];
        if (!x) primes.emplace_back(x = i);
        for (int j = 0; primes[j] <= N / i; j++) {
            comp[i * primes[j]] = primes[j];
            if (primes[j] >= x) break;
        }
    }
}
int t, n, k;

vi taken;
int GCD = 1;

int bad[N];

//backtracks over all values of y where y's upper k factors are the upper k factors of GCD AND any other factors weren't taken in x
ll test(int v, int pid, int e) {

    if (pid >= e || v > n / primes[pid]) return 1;
    ll ans = 0;
    if (!bad[pid]) {
        v *= primes[pid];
        ans += test(v, pid, e);
        v /= primes[pid];
    }
    ans += test(v, pid + 1, e);
    return ans;
}

//backtracks over all values of x where x's lower k factors are the lower k factors of GCD
ll all(int v, int pid) {
    if (pid >= SZ(primes) || v > n / primes[pid]) return test(GCD, 0, taken[k] + 1);
    ll ans = 0;
    v *= primes[pid];
    ++bad[pid];
    ans += all(v, pid);
    --bad[pid];
    v /= primes[pid];
    ans += all(v, pid + 1);
    return ans;
}

//backtracks over all possible values that have exactly 2k factors
ll take(int pid, int need) {
    if (need == 0) return all(GCD, taken[k - 1]);
    if (pid >= SZ(primes) || GCD > n / primes[pid]) return 0;
    ll ans = 0;
    taken.push_back(pid);
    GCD *= primes[pid];
    ans += take(pid, need - 1);
    GCD /= primes[pid];
    taken.pop_back();
    ans += take(pid + 1, need);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
#ifdef CLION
    freopen("in", "rt", stdin);
#endif
    sieve();

    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &k);
        if (k > 8) {
            puts("0");
            continue;
        }
        printf("%lld\n", take(0, 2 * k));
    }
}