Collecting Coins

In a strange village, people have very long names. For example: aaaaa, bbb and abababab.

You see, it's very inconvenient to call a person, so people invented a good way: just call a prefix of the names. For example, if you want to call `aaaaa', you can call `aaa', because no other names start
with `aaa'. However, you can't call `a', because two people's names start with `a'. The people in the village are smart enough to always call the shortest possible prefix.
It is guaranteed that no name is a prefix of another name (as a result, no two names can be equal).

If someone in the village wants to call every person (including himself/herself) in the village exactly once, how many characters will he/she use?

intput

The first line contains T (T10),
the number of test cases. Each test case begins with a line of one integer n ( 1n1000),
the number of people in the village. Each of the following n lines
contains a string consisting of lowercase letters, representing the name of a person. The sum of lengths of all the names in a test case does not exceed 1,000,000.

output

For each test case, print the total number of characters needed.

sample input

1
3
aaaaa
bbb
abababab

sample output
5
题目大意： 
有一个村庄他们人取名字比较特殊，像有人取名aaaaa，有bbb，也有abababaab等等奇葩的名字，现在问你用多少名字（字母）可以区分这个村庄的人。
案例分析： 像案例你可以用aa代表第一个人的名字，用b代表第二个人的名字，用ab代表地三个人的名字。 aa含有2个字母，b只有一个字母，ab含有2个字母；
所以至少要用5个字母区分这个村庄的人们。（一个村庄只有三个人，这村庄可真小的说）。


算法分析：

可以先给所有人的名字排一下序，然后顺序进行比较；详细看代码；



程序代码：

/*  1  */
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;


#define N 1005
struct Node
{
	char str[N];
}s[N];


int cmp(Node a,Node b)//结构体排序   
{
	return strcmp(a.str,b.str) < 0;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=0; i<n; i++)
			scanf("%s",s[i].str);
		sort(s,s+n,cmp);					// 对结构体排序
		int pos = 0,ans = 0;
		for(int i=0; i<n-1; i++)
		{
			for(int j=0; j<strlen(s[i].str); j++)
			{
				if(s[i].str[j] != s[i+1].str[j])
				{
					ans += max(pos,j+1);
					pos = j+1;
					break;
				}
			}
		}
		printf("%d\n",ans+pos);//最后一组还要加上
	}
	return 0;
}
/*   2      */
//#include <cstring>
//#include <iostream>
//#include <cstdlib>
//#include <algorithm>
//#include <sstream>//str[i].size() 有用
//using namespace std;
//
//#define N 10000
//
//string str[N];
//
//int main()
//{
//	int T;
//	cin >> T;
//	while(T--)
//	{
//		int n;
//		cin >> n;
//		for(int i=0; i<n; i++)
//			cin >> str[i];
//		sort(str,str+n);
//		int pos = 0,ans = 0;
//		for(int i=0; i<n-1; i++)
//		{
//			for(int j=0; j<str[i].size(); j++)
//			{
//				if(str[i][j] != str[i+1][j])
//				{
//					ans += max(pos,j+1);
//					pos = j+1;
//					break;
//				}
//			}
//		}
//		cout << ans+pos << endl;//最后一组还要加上
//	}
//	return 0;
//}