BLACKBOARD BONANZA

Alice and Bob both have lots of candies but want more. They decide to play the following turn-based game.

First they write some words on a few pieces of paper and put them into a bag so they cannot see the words. Next they decide whose turn is first. The first turn begins with the first player drawing and keeping a piece of paper with the word A from the bag and copying A onto a blackboard evenly spaced.

Then the second player draws and keeps a piece of paper with the word B on it. The current player is to write B on the blackboard underneath A evenly spaced. The second player receives one candy from the first for each character that matches vertically between A and B.

Now it is the first player’s turn who similarly draws and places word C underneath B and gains a candy for each of the characters vertically matched between B and C. The game continues until there are no more words in the bag.

What is the maximum number of candies that one of Alice and Bob will get in a turn?

The game on the second blackboard awards the second player one candy. The game on the third blackboard awards the second player two candies.

Program Input

The first line of the input contains an integer t (1 ≤ t ≤ 70), the number of test cases. Each test case starts with an integer n (2 ≤ n ≤ 70), the number of words in the bag. Then follow n lines containing one word each (in no particular order). Each word will contain between 1 and 70 characters, all of them uppercase letters of English alphabet.

Program Output

For each test case, print a line containing the maximum number of candies either Alice or Bob can get in a single turn.

Sample Input & Output

INPUT

2
2
ALICE
BOB
2
ABCB
BCAB

OUTPUT

0
2

Calgary Collegiate Programming Contest 2008