10693 PKKJ的生日礼物

时间限制:1000MS  内存限制:65535K

题型: 编程题   语言: 无限制

 

Description

写下这题目的时间是11.24，美国时间也是11.24，以此题祝远在美帝的PKKJ彭教主生日快乐。    生日嘛，自然少不了生日礼物的啦。这天彭教主收到来自中国的一份神秘的生日礼物（传说中是个漂亮的MM o(∩_∩)o 哈哈）。可是礼物却被一个密码锁锁了起来（pkkj大叫一声：坑爹啊，哪个家伙这么缺德~-_-b）。在礼物箱上还附着一张纸条：嘿嘿~想知道密码吗？那就把下面的题目解出来，答案就是密码啦！    对于一个字符串，定义它的前缀就是指字符串的任意首部。例如字符串abc的前缀有空串，a，ab，abc。    对于一个字符串集合，如果集合中任一个元素都不是其他元素的前缀的话，我们称之为完美非前缀集合。举个例子：｛”happy”, “birthday”, “to”, “pkkj”｝就是一个完美非前缀集合，而{“happy”, “hat”, “h”}就不是完美非前缀集合。    现在问题来了，给你一个字符串集合，你要找出一个该集合的子集，使得该子集是一个完美非前缀集合，且包含最多的元素。问你这个完美非前缀子集最多包含多少个元素？    由于彭教主一心只想着礼物里面的神秘MM，正所谓一心不能二用，所以他想让你帮他来解决这个难题。

 

Input

第一行只有一个正整数T，表示题目共有T组数据    对于每组数据，输入一个整数n （ 0< n <= 50 ），    接下来有n行，每行输入一个字符串，字符串由小写字母（’a’~’z’）组成，且长度不超过50．

Output

对于每组数据每行输出一个整数，代表一个完美非前缀子集最多包含多少个元素。

 

Sample Input

24happybirthdaytopkkj4happyhathha

 

Sample Output

42

 

Hint

对于第一组数据：该集合本身就是一个完美非前缀集合，所以包含最多元素的完美非前缀子集就是它本身，一共有4个元素对于第二组数据，｛”happy”,”hat”｝是其中一个的包含最多元素的完美非前缀子集，其元素个数为2 //以下为AC代码

#include
    
     #include
     
      void process(){	int n,i,j,leni,lenj,lenmin,cnt,same[52]={0};	char str[52][52]={'\0'},temp[52]={'\0'};	scanf("%d",&n);	for(i=1;i<=n;i++)		scanf("%s",str[i]);			cnt=0;	for(i=1;i