Bazinga

For n given strings S1,S2,?,Sn, labelled from 1 to n, you should find the largest i (1≤i≤n) such that there exists an integer j (1≤j<i) and Sj is not a substring of Si.

Input

The first line contains an integer t (1≤t≤50) which is the number of test cases.

For each test case, the first line is the positive integer n (1≤n≤500) and in the following n lines list are the strings S1,S2,?,Sn.

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

abc

zabc

abcd

zabcd

you

lovinyou

aboutlovinyou

allaboutlovinyou

def

abcd

abcde

abcdef

ccc

Sample Output

Case #1: 4

Case #2: -1

Case #3: 4

Case #4: 3

题意： T组数据每组数据给出n个字符串要求找出第i个串（i要尽可能的大）不包含i之前的某个或多个字符串

分析： dfs写从最后一个字符串向前搜找到相邻的2个不互相包含的字符串，

#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int oo = 1e9+7;
const int maxn = 1e6+7;
char str[510][2010];
int n, ans;
void dfs(int x)
{
    int i;
    if(x <= 1 || ans == n) return ;
    if(strstr(str[x], str[x-1])!=NULL)
        dfs(x-1);
    else
    {
        for(i = n; i > x-1; i--)///搜到当前位置
        {
            if(strstr(str[i], str[x-1]) == NULL)
            {
                ans = max(i, ans);
            }
        }
        dfs(x-1);///可能还会存在前面的字符串符合条件  继续搜。
    }
}
int main()
{
    int i, T, cas=1;
    scanf("%d", &T);
    while(T--)
    {
        ans = -1;
        scanf("%d", &n);
        for(i = 1; i <= n; i++)
          scanf("%s", str[i]);

        dfs(n);

        printf("Case #%d: %d
", cas++, ans);
    }
    return 0;
}