Longest Common Prefix for Identifier Strings

Given several test cases, each test case consists of a list of entries. Each entry has an identifier and a corresponding string. Also, a query identifier is provided. Your task is to extract all strings whose identifier matches the query and then compute the longest common prefix among these strings.

More formally, for a list of strings \(S = [s_1, s_2, \dots, s_k]\), you must find the longest string \(P\) such that \(P\) is a prefix of every \(s_i\) in \(S\). If no such prefix exists, output an empty string. Use the standard algorithm which reduces the candidate prefix gradually, i.e., if the current prefix does not match a string, repeatedly remove the last character until it matches or becomes empty.

Note: The input will be provided via standard input and the output should be produced to standard output.

inputFormat

The input consists of multiple test cases. 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 entries. The next \(N\) lines each contain an identifier and a string (separated by a space). The line following these \(N\) lines contains the query identifier. All input is read from standard input.

Example:

2
4
id1 banana
id1 bandana
id2 candy
id1 banner
id1
3
id3 apple
id3 apricot
id3 avocado
id3

outputFormat

For each test case, output a single line containing the longest common prefix for all strings whose identifier matches the query. If no such string exists or no common prefix is found, output an empty line. All output should be printed to standard output.

Example Output:

ban
a

## sample

2
4
id1 banana
id1 bandana
id2 candy
id1 banner
id1
3
id3 apple
id3 apricot
id3 avocado
id3

ban
a

</p>