#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));
}
}
I2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCgojZGVmaW5lIGVuZGwgJ1xuJwojZGVmaW5lIFNaKHYpIGludCgodikuc2l6ZSgpKQp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKY29uc3QgaW50IE4gPSAxZTUgKyA3LCBNID0gMiAqIE47CnVzaW5nIHZpID0gdmVjdG9yPGludD47CgppbnQgY29tcFtOICsgMV07CnZpIHByaW1lczsKdm9pZCBzaWV2ZSgpIHsKICAgIGZvciAoaW50IGkgPSAyOyBpIDw9IE47ICsraSkgewogICAgICAgIGludCAmeCA9IGNvbXBbaV07CiAgICAgICAgaWYgKCF4KSBwcmltZXMuZW1wbGFjZV9iYWNrKHggPSBpKTsKICAgICAgICBmb3IgKGludCBqID0gMDsgcHJpbWVzW2pdIDw9IE4gLyBpOyBqKyspIHsKICAgICAgICAgICAgY29tcFtpICogcHJpbWVzW2pdXSA9IHByaW1lc1tqXTsKICAgICAgICAgICAgaWYgKHByaW1lc1tqXSA+PSB4KSBicmVhazsKICAgICAgICB9CiAgICB9Cn0KaW50IHQsIG4sIGs7Cgp2aSB0YWtlbjsKaW50IEdDRCA9IDE7CgppbnQgYmFkW05dOwoKLy9iYWNrdHJhY2tzIG92ZXIgYWxsIHZhbHVlcyBvZiB5IHdoZXJlIHkncyB1cHBlciBrIGZhY3RvcnMgYXJlIHRoZSB1cHBlciBrIGZhY3RvcnMgb2YgR0NEIEFORCBhbnkgb3RoZXIgZmFjdG9ycyB3ZXJlbid0IHRha2VuIGluIHgKbGwgdGVzdChpbnQgdiwgaW50IHBpZCwgaW50IGUpIHsKCiAgICBpZiAocGlkID49IGUgfHwgdiA+IG4gLyBwcmltZXNbcGlkXSkgcmV0dXJuIDE7CiAgICBsbCBhbnMgPSAwOwogICAgaWYgKCFiYWRbcGlkXSkgewogICAgICAgIHYgKj0gcHJpbWVzW3BpZF07CiAgICAgICAgYW5zICs9IHRlc3QodiwgcGlkLCBlKTsKICAgICAgICB2IC89IHByaW1lc1twaWRdOwogICAgfQogICAgYW5zICs9IHRlc3QodiwgcGlkICsgMSwgZSk7CiAgICByZXR1cm4gYW5zOwp9CgovL2JhY2t0cmFja3Mgb3ZlciBhbGwgdmFsdWVzIG9mIHggd2hlcmUgeCdzIGxvd2VyIGsgZmFjdG9ycyBhcmUgdGhlIGxvd2VyIGsgZmFjdG9ycyBvZiBHQ0QKbGwgYWxsKGludCB2LCBpbnQgcGlkKSB7CiAgICBpZiAocGlkID49IFNaKHByaW1lcykgfHwgdiA+IG4gLyBwcmltZXNbcGlkXSkgcmV0dXJuIHRlc3QoR0NELCAwLCB0YWtlbltrXSArIDEpOwogICAgbGwgYW5zID0gMDsKICAgIHYgKj0gcHJpbWVzW3BpZF07CiAgICArK2JhZFtwaWRdOwogICAgYW5zICs9IGFsbCh2LCBwaWQpOwogICAgLS1iYWRbcGlkXTsKICAgIHYgLz0gcHJpbWVzW3BpZF07CiAgICBhbnMgKz0gYWxsKHYsIHBpZCArIDEpOwogICAgcmV0dXJuIGFuczsKfQoKLy9iYWNrdHJhY2tzIG92ZXIgYWxsIHBvc3NpYmxlIHZhbHVlcyB0aGF0IGhhdmUgZXhhY3RseSAyayBmYWN0b3JzCmxsIHRha2UoaW50IHBpZCwgaW50IG5lZWQpIHsKICAgIGlmIChuZWVkID09IDApIHJldHVybiBhbGwoR0NELCB0YWtlbltrIC0gMV0pOwogICAgaWYgKHBpZCA+PSBTWihwcmltZXMpIHx8IEdDRCA+IG4gLyBwcmltZXNbcGlkXSkgcmV0dXJuIDA7CiAgICBsbCBhbnMgPSAwOwogICAgdGFrZW4ucHVzaF9iYWNrKHBpZCk7CiAgICBHQ0QgKj0gcHJpbWVzW3BpZF07CiAgICBhbnMgKz0gdGFrZShwaWQsIG5lZWQgLSAxKTsKICAgIEdDRCAvPSBwcmltZXNbcGlkXTsKICAgIHRha2VuLnBvcF9iYWNrKCk7CiAgICBhbnMgKz0gdGFrZShwaWQgKyAxLCBuZWVkKTsKICAgIHJldHVybiBhbnM7Cn0KCmludCBtYWluKCkgewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKSwgY2luLnRpZSgwKTsKI2lmZGVmIENMSU9OCiAgICBmcmVvcGVuKCJpbiIsICJydCIsIHN0ZGluKTsKI2VuZGlmCiAgICBzaWV2ZSgpOwoKICAgIHNjYW5mKCIlZCIsICZ0KTsKICAgIHdoaWxlICh0LS0pIHsKICAgICAgICBzY2FuZigiJWQlZCIsICZuLCAmayk7CiAgICAgICAgaWYgKGsgPiA4KSB7CiAgICAgICAgICAgIHB1dHMoIjAiKTsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQogICAgICAgIHByaW50ZigiJWxsZFxuIiwgdGFrZSgwLCAyICogaykpOwogICAgfQp9Cg==