/**
题目：hdu6125 Free from square
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6125
题意：
从不大于n的所有正整数中选出至少1个且至多k个使得乘积不包含平方因子，对10^9+7取模。
1≤n,k≤500。
思路：
分组背包+状态压缩
把n个数分成若干组，互斥的放在同一组。 一开始把所有含平方因子的数去除掉，剩下的进行分组。 <sqrt(500)的八个素因子，编成八组，分别为包含2,3,5,7,11,13,17,19素因子的数。 注意包含的数不能重复。
>sqrt(500)的素因子，每一组为包含该素因子的数。
1这个数为一组. 因为其他组可能包含2,3,5,7,11,13,17,19；也就是这八个素因子在其他组也可能出现。 为了判断用状态压缩处理。 dp[k][s]表示选k个，前8个素因子选择状态为s时候的方法数。 dp[k][s] += dp[k-1][s-s1]; (s&s1==s1) memset(dp, 0, sizeof dp);
dp[0][0] = 1; ans = sigma[1<=i<=m]sigma[0<=s<(1<<8)]dp[i][s];
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int, int> P;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + ;
const int maxn = ;
int prime[maxn], tot;
int pos[];
vector<P> v[maxn];
int vis[maxn];
LL dp[maxn][<<];
void init()
{
for(int i = ; i < maxn; i++){
if(prime[i]==){
for(int j = i*; j < maxn; j+=i){
prime[j] = ;
}
}
}
tot = ;
for(int i = ; i < maxn; i++){
if(prime[i]==){
prime[++tot] = i;
}
}
for(int i = ; i <= ; i++){
pos[prime[i]] = i-;
}
for(int i = ; i < maxn; i++){
int x = i;
for(int j = ; j <= tot&&prime[j]<=tot; j++){
int cnt = ;
if(x%prime[j]==){
while(x%prime[j]==){
x/=prime[j];
cnt++;
}
if(cnt>){
vis[i] = ; break;
}
}
}
}
v[].push_back(P(,));///表示1这个数。
for(int i = ; i <= tot; i++){
for(int j = prime[i]; j < maxn; j+=prime[i]){
if(vis[j]) continue;
int s = ;
for(int k = ; k <= ; k++){
if(j%prime[k]==){
s |= (<<pos[prime[k]]);
}
}
v[i].push_back(P(j,s));
vis[j] = ;
}
}
for(int i = ; i <= ; i++){
for(int j = prime[i]; j < maxn; j+=prime[i]){
if(vis[j]) continue;
int s = ;
for(int k = ; k <= ; k++){
if(j%prime[k]==){
s |= (<<pos[prime[k]]);
}
}
v[i].push_back(P(j,s));
vis[j] = ;
}
} }
LL solve(int n,int m)
{
ms(dp,);
dp[][] = ;
int len = <<;
for(int i = ; i <= tot; i++){
if(prime[i]>n) break;
for(int j = m; j >= ; j--){
for(int k = ; k < (int)v[i].size(); k++){
if(v[i][k].first>n) continue;
for(int s = ; s < len; s++){
if((s&v[i][k].second)==v[i][k].second){
dp[j][s] = (dp[j][s]+dp[j-][s-v[i][k].second])%mod;
}
}
}
}
}
LL ans = ;
for(int i = ; i <= m; i++)
for(int s = ; s < len; s++)
ans = (ans+dp[i][s]) %mod;
return ans;
}
int main()
{
init();
int T;
int n, k;
cin>>T;
while(T--)
{
scanf("%d%d",&n,&k);
printf("%lld\n",solve(n,k));
} return ;
}