Time Limit: 3000 MS    Memory Limit: 65536 K 


Description

At the break of an English class, a382050365 and Power were so bored that decided to play a word puzzle to kill time. This game follows the following rules: 1> They in turn say a word containing only vowel (A, E, I, O, U) and the next word being said should exactly begin with the same letter as the last letter of the former word. 2> It can starts with only a single word. 3> Each word can be said only once and must be contained in the dictionary. 4> The total length all the word used in the game is defined as the complexity of the game. Tian found it¡¯s hard to end the game in a short time. So he had a question .What¡¯s the max complexity of the game based on a certain dictionary.

Input

The first line is an integer T which stands for the number of test cases. For each test case, The first line contains only one integer N( 1<= N <= 16) which indicates the amount of dictionary . Each following line contains a certain word in the dictionary and each word is a string consist of A, E, I, O, U. The length of each words is not more than 100, and all words are distinct.

Output

For each test case , output one line with an integer indicating the max complexity.

Sample Input

2 3 AE A IA 2 AI OUE

Sample Output

5 3

Author

TLE power/a382050365/hanchao717 Translated by Mo MEI

Source

Sichuan University Programming Contest 2011 Preliminary