#include <bits/stdc++.h>
using namespace std;
#define GG ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
bool isPossible(string x,int xx,string b,int m)
{ 
	    int i=0; char c=x[i];
		for(int j=0;j<m;j++)
		{	if(b[j]==c)
			{  if(i==(x.size()-1) )
			   return 1;
			   else
			   {i++; c=x[i];
			   }
			}
 
		}
		return 0;
 
}
 
 
 
 
int main () { GG;
int t; cin>>t;
while(t--) {
int n,m;	string a,b;
cin>>n>>m>>a>>b;
cout<<isPossible("1",3,b,m)<<"\n";
}return 0;}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgR0cgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwpib29sIGlzUG9zc2libGUoc3RyaW5nIHgsaW50IHh4LHN0cmluZyBiLGludCBtKQp7IAoJICAgIGludCBpPTA7IGNoYXIgYz14W2ldOwoJCWZvcihpbnQgaj0wO2o8bTtqKyspCgkJewlpZihiW2pdPT1jKQoJCQl7ICBpZihpPT0oeC5zaXplKCktMSkgKQoJCQkgICByZXR1cm4gMTsKCQkJICAgZWxzZQoJCQkgICB7aSsrOyBjPXhbaV07CgkJCSAgIH0KCQkJfQoJCQkKCQl9CgkJcmV0dXJuIDA7Cgp9CgoKCgppbnQgbWFpbiAoKSB7IEdHOwppbnQgdDsgY2luPj50Owp3aGlsZSh0LS0pIHsKaW50IG4sbTsJc3RyaW5nIGEsYjsKY2luPj5uPj5tPj5hPj5iOwpjb3V0PDxpc1Bvc3NpYmxlKCIxIiwzLGIsbSk8PCJcbiI7Cn1yZXR1cm4gMDt9

MQo1IDQKMTAwMTEKMTExMA==

1
5 4
10011
1110