Migrated from Lutece 396 Game

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

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\leq N\leq 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.

Samples

2
3
AE
A
IA
2
AI
OUE

5
3

Resources

10th SCU Programming Contest Final