Bazinga
Time Limit: 1000ms
Memory Limit: 65536KB
This problem will be judged on HDU. Original ID: 5510 64-bit integer IO format: %I64d Java class name: Main
Description
Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.
For $n$ given strings $S_1,S_2,\cdots,S_n$, labelled from $1$ to $n$, you should find the largest $i~(1\le i\le n)$ such that there exists an integer $j~(1\le j<i)$ and $S_j$ is not a substring of $S_i$.
A substring of a string $S_i$ is another string that occurs in $S_i$. For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".
Don't tilt your head. I'm serious.
For $n$ given strings $S_1,S_2,\cdots,S_n$, labelled from $1$ to $n$, you should find the largest $i~(1\le i\le n)$ such that there exists an integer $j~(1\le j<i)$ and $S_j$ is not a substring of $S_i$.
A substring of a string $S_i$ is another string that occurs in $S_i$. For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".
Input
The first line contains an integer $t~(1\le t\le 50)$ which is the number of test cases.
For each test case, the first line is the positive integer $n~(1\le n\le 500)$ and in the following $n$ lines list are the strings $S_1,S_2,\cdots,S_n$.
All strings are given in lower-case letters and strings are no longer than $2000$ letters.
For each test case, the first line is the positive integer $n~(1\le n\le 500)$ and in the following $n$ lines list are the strings $S_1,S_2,\cdots,S_n$.
All strings are given in lower-case letters and strings are no longer than $2000$ letters.
Output
For each test case, output the largest label you get. If it does not exist, output $-1$.
Sample Input
4 5 ab abc zabc abcd zabcd 4 you lovinyou aboutlovinyou allaboutlovinyou 5 de def abcd abcde abcdef 3 a ba ccc
Sample Output
Case #1: 4 Case #2: -1 Case #3: 4 Case #4: 3