Longest Word Chain

Given a list of words, your task is to find the length of the longest chain of words where each successive word is obtained by removing exactly one character from the previous word. Formally, a word w' is a child of word w if w' can be obtained by deleting exactly one letter from w and w' exists in the list. Every word is considered to be a chain of length 1 by itself.

For each test case, you are given an integer n and a list of n words. Compute the maximum chain length possible among all words in that list.

For example, given the list ["a", "ba", "bca", "bdca", "abc"], one of the longest chains is "bdca" -> "bca" -> "ba" -> "a", whose length is 4.

The relation can be expressed using the formula in \(\LaTeX\) as follows:

\[ \text{chain}(w) = \max\Big\{1,\;1+\text{chain}(w')\;:\; w'\text{ is obtained by deleting one letter from }w\Big\} \]

inputFormat

The input is given via standard input (stdin) and has the following format:

T
n1
word1
word2
... 
word n1
n2
word1
word2
... 
word n2
...

Here, T is the number of test cases. For each test case, the first line contains a single integer n which is the number of words in that test case, followed by n lines each containing one word.

outputFormat

For each test case, output a single integer on a new line that represents the length of the longest word chain possible.

## sample

1
5
a
ba
bca
bdca
abc

4

</p>