J. Similarity (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The easy version and the hard version are different problems, yet it is crucial to retain your solution code once it's accepted, as it might be useful later on.

Many place names bear similarities. Take, for instance, $$$\texttt{Suzhou}$$$ and $$$\texttt{Quzhou}$$$. They are considered similar because they share a common substring $$$\texttt{uzhou}$$$. A substring is a contiguous sequence of characters within a string. For example, in the string $$$\texttt{abcd}$$$, $$$\texttt{bc}$$$ is a substring of it, but $$$\texttt{ac}$$$ is not.

We define the similarity between two strings as the length of their longest common substring. Thus, the similarity between $$$\texttt{Suzhou}$$$ and $$$\texttt{Quzhou}$$$ is $$$5$$$, and between $$$\texttt{Hangzhou}$$$ and $$$\texttt{Chengdu}$$$ it is $$$2$$$.

Given $$$n$$$ place names, your task is to find two names that have the maximum similarity and output the similarity.

Input

The first line contains one integer $$$T$$$ ($$$1\le T\le 15$$$), indicating the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$2\le n \le 50$$$), indicating the number of places. Each of the following $$$n$$$ lines contains a string $$$s$$$ ($$$1 \le |s| \le 50$$$), indicating the place names. The place names are guaranteed to consist only of lowercase English letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300$$$.

Output

For each test case, output an integer in a single line representing the maximum similarity.

Example
Input
2
2
jiangsu
xiangtan
3
hangzhou
chengdu
wuxi
Output
4
2