/*

dp[i,j][0|1|2]表示p串的第i位，s串的第j位相匹配，pi和pi-1换，pi不换，pi和pi+1换的状态下是否能匹配

dp[i,j][0] = dp[i-1,j-1][2] & p[i-1]==s[j]

dp[i,j][1] = (dp[i-1,j-1][1] || dp[i-1,j-1][2]) & p[i]==s[j]

dp[i,j][2] = (dp[i-1,j-1][0] || dp[i-1,j-1][1]) & p[i+1]==s[j]

由于dp是01数组，并且dp[i]的所有状态都由dp[i-1]得到，所以我们可以考虑用bitset优化j

观察原来的dp方程

dp[i][0]由dp[i-1][2]<<1 & p[i-1]和s[1..j] 得到

dp[i][1]由dp[i-1][1|2]<<1 & p[i]和s[1..j] 得到

dp[i][2]由dp[i-1][0|1]<<1 & p[i+1]和s[1..j] 得到

那么我们再预处理一下s数组和26个字符比较的bitset数组即可

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 100005

#define maxm 5005

bitset<maxn>dp[][];

bitset<maxn>f[];

int n,m;

char s[maxn],p[maxm];

void init(){//处理f数组

    for(int i=;i<;i++)f[i].reset();

    for(int j=;j<n;j++)f[s[j]-'a'][j]=;

}

int main(){

    int t;cin>>t;

    while(t--){

        scanf("%d%d",&n,&m);

        scanf("%s%s",&s,&p);

        init();

        for(int i=;i<;i++)

            for(int j=;j<;j++)

                dp[i][j].reset();

        //处理初始状态：即p[0]或p[1] 和s[1..j]的匹配

        dp[][]=f[p[]-'a'];

        if(m>) dp[][]=f[p[]-'a']; 

        //然后刷表从p[1]转移到p[m] ,滚动数组节省空间

        int cur=;

        for(int i=;i<m;i++){

            cur^=;

            dp[cur][]=(dp[cur^][]<<) & f[p[i-]-'a'];//这里为什么要用<<1，因为是把dp[i-1][j-1]的答案用到dp[i][j]里，等于集体左移了一次

            dp[cur][]=((dp[cur^][] | dp[cur^][])<<) & f[p[i]-'a'];

            if(i<m-)

                dp[cur][]=((dp[cur^][] | dp[cur^][])<<) & f[p[i+]-'a'];

        }

        for(int i=;i<n;i++)

            if(dp[cur][][i+m-] || dp[cur][][i+m-])cout<<;

        else cout<<;

        puts("");

    }

}