Time-division multiplexing (TDM) is a method of transmitting and receiving independent signals over a common signal path by means of synchronized switches at each end of the transmission line so that each signal appears on the line only a fraction of time in an alternating pattern. This method transmits two or more digital signals or analog signals over a common channel.
The time domain is divided into several recurrent time slots of fixed length, one for each sub-channel. A sample byte or data block of sub-channel 1 is transmitted during time slot 1, sub-channel 2 during time slot 2, etc. One TDM frame consists of one time slot per sub-channel plus a synchronization channel and sometimes error correction channel before the synchronization. After the last sub-channel, error correction, and synchronization, the cycle starts all over again with a new frame, starting with the second sample, byte or data block from sub-channel 1, etc.
There are $n$ time slots in total now, each of which periodically transmits a string only containing lowercase letters. You need to find the shortest slot length that contains all the different letters transmitted totally.
Input
This problem contains multiple test cases.
The first line contains a single integer $T$ ($1\leq T \leq 100$) indicating the number of test cases.
For each test case, the first line contains a single integer $n(1\leq n\leq 100)$. Then next $n$ lines, each line contains a string $s_i$ only containing lowercase letters. The length of each string is no more than $12$.
It is guaranteed that the $\sum n \leq 2000$.
Output
For each test case, output a single integer in a line, the answer for the test case.
SampleInput
2
2
abc
bd
2
bab
bbc
SampleOutput
4
4
Hint In the first sample, there are two time slots in total and s1 = abc, s2 = bd. Letters transmitted on the channel are as follows: abbdcbad... We can choose dcba as the answer string so the answer is 4.