/// You just can't beat the person who never gives up
/// ICPC next year
#include<bits/stdc++.h>
using namespace std ;
const int N = 1e5+5 ;
int t ,n ,k ,nxt_prime[N] ;
int spf[N];
vector<pair<int,int>> f ;
void sieve(){
for(int i=1;i<N;++i) spf[i]=i;
for(int i=2;i*i<N;++i)if(spf[i]==i){
for(int j=i*i;j<N;j+=i)if(spf[j]==j)spf[j]=i;
}
}
vector<int> factorize(int x){
vector<int> ret;
while(x!=1){
ret.push_back(spf[x]);
x/=spf[x];
}
sort(ret.begin(),ret.end());
return ret ;
}
int cnt[N] ;
long long solve3(int val,int l,int r){
if(val>n) return 0;
if(1ll*val*l>n) return 1;
if(l>r) return 1;
long long ret = solve3(val,nxt_prime[l],r);
if(cnt[l]) return ret ;
return ret + solve3(val*l,l,r);
}
long long solve2(int val,int r,int i,int rem){
if(rem==0) return solve3(val,2,r);
if(i==f.size()) return 0;
if(!f[i].second) return solve2(val,r,i+1,rem) ;
--f[i].second ;
--cnt[f[i].first] ;
long long ret = solve2(val*f[i].first,f[i].first,i,rem-1);
++f[i].second ;
++cnt[f[i].first] ;
ret += solve2(val,r,i+1,rem);
return ret ;
}
long long solve(int x){
vector<int> fac = factorize(x) ;
if(fac.size()<k+k) return 0;
int cur = 1 ;
for(int i=0;i<k;++i) cur *= fac[i] ;
reverse(fac.begin(),fac.end());
for(int i=0;i<k;++i) fac.pop_back();
reverse(fac.begin(),fac.end());
f.clear() ;
for(int i:fac){
if(!f.size() || i!=f.back().first) f.push_back({i,1});
else ++f.back().second ;
}
reverse(f.begin(),f.end());
for(auto go:f) cnt[go.first] = go.second ;
long long ret = solve2(cur,n,0,k);
for(auto go:f) cnt[go.first] = 0 ;
return ret ;
}
int main(){
sieve();
int nxt = N-1 ;
for(int i=N-1;i>=0;--i){
if(i+1<N) nxt_prime[i] = nxt ;
if(spf[i]==i) nxt = i ;
}
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
if(k>8){
puts("0") ;
continue ;
}
long long ans = 0 ;
for(int i=1;i<=n;++i) ans += solve(i) ;
printf("%lld\n",ans);
}
return 0;
}
Ly8vIFlvdSBqdXN0IGNhbid0IGJlYXQgdGhlIHBlcnNvbiB3aG8gbmV2ZXIgZ2l2ZXMgdXAKLy8vIElDUEMgbmV4dCB5ZWFyCgojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkIDsKCmNvbnN0IGludCBOID0gMWU1KzUgOwoKaW50IHQgLG4gLGsgLG54dF9wcmltZVtOXSA7CmludCBzcGZbTl07CnZlY3RvcjxwYWlyPGludCxpbnQ+PiBmIDsKdm9pZCBzaWV2ZSgpewogICAgZm9yKGludCBpPTE7aTxOOysraSkgc3BmW2ldPWk7CiAgICBmb3IoaW50IGk9MjtpKmk8TjsrK2kpaWYoc3BmW2ldPT1pKXsKICAgICAgICBmb3IoaW50IGo9aSppO2o8TjtqKz1pKWlmKHNwZltqXT09ailzcGZbal09aTsKICAgIH0KfQp2ZWN0b3I8aW50PiBmYWN0b3JpemUoaW50IHgpewogICAgdmVjdG9yPGludD4gcmV0OwogICAgd2hpbGUoeCE9MSl7CiAgICAgICAgcmV0LnB1c2hfYmFjayhzcGZbeF0pOwogICAgICAgIHgvPXNwZlt4XTsKICAgIH0KICAgIHNvcnQocmV0LmJlZ2luKCkscmV0LmVuZCgpKTsKICAgIHJldHVybiByZXQgOwp9CmludCBjbnRbTl0gOwpsb25nIGxvbmcgc29sdmUzKGludCB2YWwsaW50IGwsaW50IHIpewogICAgaWYodmFsPm4pIHJldHVybiAwOwogICAgaWYoMWxsKnZhbCpsPm4pIHJldHVybiAxOwogICAgaWYobD5yKSByZXR1cm4gMTsKICAgIGxvbmcgbG9uZyByZXQgPSBzb2x2ZTModmFsLG54dF9wcmltZVtsXSxyKTsKICAgIGlmKGNudFtsXSkgcmV0dXJuIHJldCA7CiAgICByZXR1cm4gcmV0ICsgc29sdmUzKHZhbCpsLGwscik7Cn0KbG9uZyBsb25nIHNvbHZlMihpbnQgdmFsLGludCByLGludCBpLGludCByZW0pewogICAgaWYocmVtPT0wKSByZXR1cm4gc29sdmUzKHZhbCwyLHIpOwogICAgaWYoaT09Zi5zaXplKCkpIHJldHVybiAwOwogICAgaWYoIWZbaV0uc2Vjb25kKSByZXR1cm4gc29sdmUyKHZhbCxyLGkrMSxyZW0pIDsKICAgIC0tZltpXS5zZWNvbmQgOwogICAgLS1jbnRbZltpXS5maXJzdF0gOwogICAgbG9uZyBsb25nIHJldCA9IHNvbHZlMih2YWwqZltpXS5maXJzdCxmW2ldLmZpcnN0LGkscmVtLTEpOwogICAgKytmW2ldLnNlY29uZCA7CiAgICArK2NudFtmW2ldLmZpcnN0XSA7CiAgICByZXQgKz0gc29sdmUyKHZhbCxyLGkrMSxyZW0pOwogICAgcmV0dXJuIHJldCA7Cn0KbG9uZyBsb25nIHNvbHZlKGludCB4KXsKICAgIHZlY3RvcjxpbnQ+IGZhYyA9IGZhY3Rvcml6ZSh4KSA7CiAgICBpZihmYWMuc2l6ZSgpPGsraykgcmV0dXJuIDA7CiAgICBpbnQgY3VyID0gMSA7CiAgICBmb3IoaW50IGk9MDtpPGs7KytpKSBjdXIgKj0gZmFjW2ldIDsKICAgIHJldmVyc2UoZmFjLmJlZ2luKCksZmFjLmVuZCgpKTsKICAgIGZvcihpbnQgaT0wO2k8azsrK2kpIGZhYy5wb3BfYmFjaygpOwogICAgcmV2ZXJzZShmYWMuYmVnaW4oKSxmYWMuZW5kKCkpOwogICAgZi5jbGVhcigpIDsKICAgIGZvcihpbnQgaTpmYWMpewogICAgICAgIGlmKCFmLnNpemUoKSB8fCBpIT1mLmJhY2soKS5maXJzdCkgZi5wdXNoX2JhY2soe2ksMX0pOwogICAgICAgIGVsc2UgKytmLmJhY2soKS5zZWNvbmQgOwogICAgfQogICAgcmV2ZXJzZShmLmJlZ2luKCksZi5lbmQoKSk7CiAgICBmb3IoYXV0byBnbzpmKSBjbnRbZ28uZmlyc3RdID0gZ28uc2Vjb25kIDsKICAgIGxvbmcgbG9uZyByZXQgPSAgc29sdmUyKGN1cixuLDAsayk7CiAgICBmb3IoYXV0byBnbzpmKSBjbnRbZ28uZmlyc3RdID0gMCA7CiAgICByZXR1cm4gcmV0IDsKfQppbnQgbWFpbigpewogICAgc2lldmUoKTsKICAgIGludCBueHQgPSBOLTEgOwogICAgZm9yKGludCBpPU4tMTtpPj0wOy0taSl7CiAgICAgICAgaWYoaSsxPE4pIG54dF9wcmltZVtpXSA9IG54dCA7CiAgICAgICAgaWYoc3BmW2ldPT1pKSBueHQgPSBpIDsKICAgIH0KCiAgICBzY2FuZigiJWQiLCZ0KTsKICAgIHdoaWxlKHQtLSl7CiAgICAgICAgc2NhbmYoIiVkJWQiLCZuLCZrKTsKICAgICAgICBpZihrPjgpewogICAgICAgICAgICBwdXRzKCIwIikgOwogICAgICAgICAgICBjb250aW51ZSA7CiAgICAgICAgfQogICAgICAgIGxvbmcgbG9uZyBhbnMgPSAwIDsKICAgICAgICBmb3IoaW50IGk9MTtpPD1uOysraSkgYW5zICs9IHNvbHZlKGkpIDsKICAgICAgICBwcmludGYoIiVsbGRcbiIsYW5zKTsKICAgIH0KCiAgICByZXR1cm4gMDsKfQo=