#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define mod 1000000007
int T,n,k;
int q[95]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,
233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499};
int a[96][96][256],vis[96][96][256];
int a1[256][9],vis1[256][9];
int subsol(int sg,int k)//可选取范围在小于根号N范围
{
int res;
if(k>8)k=8;
if(k<0)return 0;//不再选
if(sg==0) return 1;//可选范围为0;那么这一支的贡献返回1,如果把这种选择看成一棵树的话;
if(vis1[sg][k]) return a1[sg][k];
int a=0;
while((1<<a)<=sg)a++;a--;
res=subsol(sg^(1<<a),k);//不取q[a];
for(int i=0;i<(1<<a);i++)
if((sg&i)==i)//i组合状态合法
{
int s=q[a];
for(int j=0;j<a;j++)
{
if(i&(1<<j))//j是选好的质数
{
s*=q[j];
if(s>n)break;
}
}
if(s<=n)(res+=subsol(sg^(1<<a)^i,k-1))%=mod;
}
vis1[sg][k]=1;
return a1[sg][k]=res;
}
int sol(int lim,int m,int k,int sg)
{
int res;
if(k<0)return 0;//不在取
if(m<lim) return subsol(sg,k);//大于根号n的质数已经枚举完了
if(vis[m][k][sg]) return a[m][k][sg];//取第m个且在sg的范围内取K个
//可以知道这里m都是大于根号n的质数
res=sol(lim,m-1,k,sg);//不选q[m]的情况
for(int i=0;i<=255;i++)
{
if((sg&i)==i)//如果i在可选区间内,就选
{
int s=q[m];//q[m]必选
for(int j=0;j<=7;j++)//找出选的那些位
if(i&(1<<j))
{
s*=q[j];
if(s>n)break;//这个数选多了。这个组合不成立
}
if(s<=n)//这个组合选取成功,找到了一个数,现在找下一个数
(res+=sol(lim,m-1,k-1,sg^i))%=mod;//q[m]不能再选了,可选范围也去掉了选过的那些质数
}
}
vis[m][k][sg]=1;//当前值已经找到,省去了重复计算
return a[m][k][sg]=res;
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
memset(vis,0,sizeof vis);
memset(vis1,0,sizeof vis1);
if(k>95)k=95;
double h=sqrt(n)+1e-6;
int a=0;while(q[a]<=h)a++;
int b=0;while(q[b]<=n&&b<95)b++;
int ans=sol(a,b-1,k,(1<<a)-1)+sol(a,b-1,k-1,(1<<a)-1)-1;
printf("%d
",ans%mod);//不包含1+包含1-空
}
return 0;
}
反向思维,从质因数乘积组成成合法序列入手,可以抽象成一颗乘积的组合树,每一支里面选择的质数互斥;