#include <bits/stdc++.h>
using namespace std;
struct Node
{
vector<Node*> child ;
bool is ;
Node()
{
child.resize(26 , NULL) ;
is = false;
}
};
class Trie{
Node *root ;
public:
Trie()
{
root = new Node() ;
}
void insert(string s)
{
Node *cur = root ;
int i = 0 ;
while(i < s.length())
{
if(cur -> child[s[i] - 'a'] == NULL)
cur -> child[s[i] - 'a'] = new Node();
cur = cur -> child[s[i] - 'a'] ;
i ++ ;
}
cur -> is = true ;
}
void search(string &s ,int st , vector<bool> &dp)
{
Node *cur = root ;
for(int i = st ; i < s.length() ; i ++ )
{
if(cur == NULL)
return ;
cur = cur -> child[s[i] - 'a'] ;
if(cur && cur -> is )
dp[i + 1] = true ;
}
}
};
class Solution{
public:
int wordBreak(string A, vector<string> &B) {
//code here
Trie *tmp = new Trie();
int n = A.size() ;
vector<bool> dp(n + 1, false) ;
for(int i =0 ; i < B.size() ; i ++ )
tmp -> insert(B[i]) ;
dp[0] = true ;
for(int i = 0 ; i < A.length() ; i ++ )
{
if(dp[i])
tmp -> search( A , i , dp) ;
}
return dp[n];
}
};
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<string> dict;
for(int i=0;i<n;i++){
string S;
cin>>S;
dict.push_back(S);
}
string line;
cin>>line;
Solution ob;
cout<<ob.wordBreak(line, dict)<<"\n";
}
}