#include<bits/stdc++.h>
using namespace std;
const int maxn=305,maxm=105,maxe=30005;
int n,m,e,x[maxe],y[maxe];
int init(){
scanf("%d%d%d",&n,&m,&e);
for (int i=1;i<=e;++i) scanf("%d%d",&x[i],&y[i]);
if (n<=20&&m<=10&&e<=25) return 0;
if (e==n*m) return 1;
return 2;
}
namespace task1{
typedef vector<int>::iterator iter;
vector<int> g[maxn];
int fmx,cur[maxn],ans[maxn];
void check(){
static int cnt[maxm];memset(cnt+1,0,sizeof(int)*m);
for (int i=1;i<=n;++i) ++cnt[cur[i]];
int res=0;
for (int i=1;i<=m;++i)
if (cnt[i]>3) return;
else if (cnt[i]<=1) ++res;
if (res>fmx) fmx=res,memcpy(ans+1,cur+1,sizeof(int)*n);
}
void dfs(int dep){
if (dep==n+1){check();return;}
for (iter it=g[dep].begin();it!=g[dep].end();++it)
cur[dep]=*it,dfs(dep+1);
}
void work(){
for (int i=1;i<=n;++i) g[i].clear();
for (int i=1;i<=e;++i) g[x[i]].push_back(y[i]);
fmx=-1,dfs(1);
printf("%d
",fmx);
for (int i=1;i<=n;++i) printf(i==n?"%d
":"%d ",ans[i]);
}
}
namespace task2{
int fmx,ans[maxn];
void work(){
if (n<=m){
fmx=m;
for (int i=1;i<=n;++i) ans[i]=i;
}
else{
static int cur,cnt[maxm];memset(cnt+1,0,sizeof(int)*m);
for (cur=1;cur<=m;++cur) ++cnt[cur],ans[cur]=cur;
for (int i=1;i<=m&&cur<=n;++i,++cur){
ans[cur]=i,++cnt[i];
if (++cur<=n) ans[cur]=i,++cnt[i];
}
fmx=0;
for (int i=1;i<=m;++i) if (cnt[i]<=1) ++fmx;
}
printf("%d
",fmx);
for (int i=1;i<=n;++i) printf(i==n?"%d
":"%d ",ans[i]);
}
}
namespace task3{
struct cost_flow{
static const int maxn=505,maxe=70005,inf=0x3f3f3f3f;
struct edge{
edge *pre,*opp;int son,val,exp;
void add(edge *p,edge *o,int s,int v,int e){pre=p,opp=o,son=s,val=v,exp=e;}
}*pos[maxn],e[maxe];
int s,t,tot;
void clear(){tot=0,memset(pos,0,sizeof(pos));}
void connect(int u,int v,int f,int c){
++tot,e[tot].add(pos[u],e+tot+1,v,f,c),pos[u]=e+tot;
++tot,e[tot].add(pos[v],e+tot-1,u,0,-c),pos[v]=e+tot;
}
int q[maxn],d[maxn];bool inq[maxn];edge *pe[maxn];
bool spfa(){
memset(d,63,sizeof(d));
memset(inq,0,sizeof(inq));
inq[s]=1,d[s]=0,pe[s]=0;
for (int u,head=0,tail=1;head!=tail;inq[u]=0){
u=q[++head==maxn?head=1:head];
for (edge *p=pos[u];p;p=p->pre)
if (p->val&&d[p->son]>d[u]+p->exp){
d[p->son]=d[u]+p->exp,pe[p->son]=p;
if (!inq[p->son]) inq[p->son]=1,q[++tail==maxn?tail=1:tail]=p->son;
}
}
return d[t]!=inf;
}
int aug(){
int flow=inf;
for (int x=t;x!=s;x=pe[x]->opp->son) flow=min(flow,pe[x]->val);
for (int x=t;x!=s;x=pe[x]->opp->son) pe[x]->val-=flow,pe[x]->opp->val+=flow;
return flow*d[t];
}
int min_cost(){
int res=0;
while (spfa()) res+=aug();
return res;
}
}g;
void work(){
g.clear(),g.s=0,g.t=n+m+1;
for (int i=1;i<=n;++i) g.connect(g.s,i,1,0);
for (int i=1;i<=m;++i) g.connect(n+i,g.t,1,0),g.connect(n+i,g.t,2,1);
for (int i=1;i<=e;++i) g.connect(x[i],n+y[i],1,0);
printf("%d
",max(0,m-g.min_cost()));
for (int i=1;i<=n;++i)
for (cost_flow::edge *p=g.pos[i];p;p=p->pre)
if (!p->val) printf(i==n?"%d
":"%d ",p->son-n);
}
}
void solve(){
int t=init();
if (!t) task1::work();
else if (t==1) task2::work();
else task3::work();
}
int main(){
freopen("npc.in","r",stdin);
freopen("npc.out","w",stdout);
int cases;scanf("%d",&cases);
while (cases--) solve();
fclose(stdin);fclose(stdout);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn=500015,maxw=100005;
char s[maxn];
bool can[maxw];
int n,w,cnt,fail[maxn],v[maxn];
void solve(){
scanf("%d%d%s",&n,&w,s+1);
fail[1]=0;
for (int j=0,i=2;i<=n;++i){
while (j&&s[j+1]!=s[i]) j=fail[j];
fail[i]=s[j+1]==s[i]?++j:0;
}
v[cnt=1]=n;
for (int x=fail[n];x;x=fail[x]) v[++cnt]=n-x;
memset(can,0,sizeof(can)),can[n]=1;
for (int i=1;i<=cnt;++i)
for (int j=n+v[i];j<=w;++j)
can[j]|=can[j-v[i]];
int res=0;
for (int i=n;i<=w;++i) res+=can[i];
printf("%d
",res);
}
int main(){
freopen("jie.in","r",stdin);
freopen("jie.out","w",stdout);
int cases;scanf("%d",&cases);
while (cases--) solve();
fclose(stdin);fclose(stdout);
return 0;
}
/*
2
44 1000
baaaaaabaabbaaabbbbabbbaaabbbababaaabaaabaaa
41 1000
abaabbabaaabaabbbbbbbbbbbababbbbaaabaabbb
*/