Find the Concatenated Word

Given multiple test cases, each test case consists of a list of words. Your task is to find a word in each list that can be formed by concatenating exactly two words from the same list. Formally, for a word ( w ) in a test case, determine if there exists an index ( i ) (with ( 1 \leq i < |w| )) such that the prefix ( w[0:i] ) and the suffix ( w[i:] ) are both present in the list. If such a word is found, output it; otherwise, output "No valid word".

Note that only one valid concatenation is required per test case. The input is read from standard input and the output is printed to standard output.

inputFormat

The first line contains an integer ( T ), the number of test cases. For each test case, the first line contains an integer ( N ) representing the number of words, followed by ( N ) lines each containing a word.

Example Input:
2
4
cat
dog
catdog
bird
3
app
le
apple

outputFormat

For each test case, output a single line containing the concatenated word if it exists, or "No valid word" if none exists.

Example Output:
catdog
apple## sample

2
4
cat
dog
catdog
bird
3
app
le
apple

catdog
apple