Server Time: Wed Feb 26, 2020 1:30 pm
Welcome ( logout
D - BAZINGA Squared
Ranklist
Time Limit: 5 second(s) Memory Limit: 64 MB

You are given n strings as initial input. Then you are queried q times. For each query you are asked the prefix of the given length, m from among input strings. As there can be many prefixes of length m, you have to choose the one that have maximum number of occurrences as prefix among all input strings. Even after this, there could be multiple prefixes that occurred same number of times among all input strings, in that case you have to print the lexicographically smallest one.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 10000) denoting the number of initial strings (consists of only lowercase English letters). Next n line contains n string. Each string length is maximum 10^3. Then there is an integer denoting number of queries, q (1 ≤ q ≤ 1000). Next q line contains an integer m. For each m, you have to print a string of length m that is a prefix of at least 1 input strings (if multiple, follow the above criteria).

Output

For each query, print the string then number of times that prefix occurred among all input strings.

If not found write “Not Found!”(without quotes).

Sample Input

Output for Sample Input

1

9

abcd

abd

abn

anb

anbdf

panbdf

qanbdf

oanbdf

zzzzzzz

7

1

2

3

4

5

6

10

Case 1:

a 5

ab 3

anb 2

abcd 1

anbdf 1

oanbdf 1

Not Found!

 


Problem Setter: S. M. IJAZ-UL-AMIN CHOWDHURY
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan