/**

题目：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 ;

}