#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int p[50],a[20];
int n,m,cnt;
void prime()
{
for(int i=1;i<=50;i++) p[i]=1;
p[1]=0;
for(int i=1;i<=50;i++)
{
for(int j=2;j<=sqrt(i);j++)
{
if(i/j*j==i)
p[i]=0;
}
}
}
void mima(int pos,int sum)
{
if(pos==n+1)
{
cnt+=1;
return;
}
if(pos<m)
{
for(int i=0;i<10;i++)
{
a[pos]=i;//不要忘了
mima(pos+1,sum+i);
}
}
else
{
for(int i=0;i<10;i++)
{
if(p[sum+i])
{
a[pos]=i;//不要忘了
mima(pos+1,sum+i-a[pos-m+1]);
}
}
}
}
int main()
{
prime();//不要忘了
int w;
cin>>w;
while(w--)
{
cnt=0;
cin>>n>>m;
mima(1,0);
cout<<cnt<<endl;
}
return 0;
}
深度遍歷
