#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";
    }
}