You are given $$$n$$$ strings $$$s_1, s_2,\dots, s_n$$$. Let $$$S = {s_1, s_2,\dots, s_n}$$$.

You are also given $$$q$$$ strings $$$t_1, t_2,\dots, t_q$$$. For each $$$i = 1, 2,\dots, q$$$, find the longest common prefix of $$$t_i$$$ and any string in $$$S$$$.

Input: First line: number of test cases ($$$\le 10^4$$$)

• First line of each test case: $$$n$$$
• Next $$$n$$$ lines: $$$s_1, s_2,\dots, s_n$$$
• Next line: $$$q$$$
• Next $$$q$$$ lines: $$$t_1, t_2,\dots, t_q$$$

Sum of string lengths is $$$\le 10^6$$$

Output: For each test case, $$$q$$$ integers: the lengths of the longest common prefixes.

2
3
a
aa
ab
5
aaa
abb
acc
baa
xyz
1
b
1
a

Output:
2 2 1 0 0
0

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6; // total length of strings
const int A = 26; // alphabet size

int trie[N][A];
int W = 1;

// clearing the trie (between testcases)
void clear(int i=0) {
    W = 1;
    for (int j = 0; j < A; ++j) {
        if (trie[i][j] != -1) clear(trie[i][j]);
        trie[i][j] = -1;
    }
}

int main() {
    memset(trie, -1, sizeof trie);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        for (int i = 0; i < n; ++i) {
            string s;
            cin >> s;
            int j = 0;
            for (char c : s) {
                if (trie[j][c-'a'] == -1) trie[j][c-'a'] = W++;
                j = trie[j][c-'a'];
            }
        }
        
        int q;
        cin >> q;
        
        for (int i = 0; i < q; ++i) {
            string s;
            cin >> s;
            
            int ans = 0;
            int j = 0;
            for (char c : s) {
                if (trie[j][c-'a'] != -1) {
                    j = trie[j][c-'a'];
                    ++ans;
                } else break;
            }
            cout << ans << ' ';    
        }
        cout << '\n';
        clear();
    }
}