Maximum String Score

 Practice Questions 

 Maximum String Score 

 Problem Statement 

You are given a list S that contains strings.

Note: Each string in the list consists of only lowercase Latin Letters.

The score of any string P is represented as follows.

• The sum of the number of strings in S in which P occurs as a substring and the number of strings in S in which P occurs as a prefix.

 Example 

If S = [ 'abc', 'abab', 'aba' ] and P = 'ab', then score of P = 3. This is because (P occurs in all the strings) + 3 (P occurs in 'abc', 'abab', and 'aba' as a prefix) = 6.

Note: If P occurs as a prefix in any of the strings, then it will also contribute to the substring.

Your task is to determine the maximum score possible of any string provided.

 Input Format 

• The first line contains T denoting the number of test cases.

• For each test case

• The first line contains the N denoting the number of strings in the list.

• The Next N lines contain the elements of the list.

 Output Format 

For each test case, print the maximum score possible in a new line.

 Constraints 

1 ≤ T ≤ 100

1 ≤ N ≤ 10⁵

 Example Input/Output 1 

 Input 

2

4

abc

cab

dfab

xy

3

aaa

aaa

aaa

 Output 

4

6

 Explanation 

In the first testcases, the maximum score is of 'ab' , which is 3 + 1 = 4. We can verify that no other string leads to a better score.

In the second testcase, the maximum score is 'aaa', which is 3 + 3 = 6. We can verify that no other string leads to a better score

 Note 

Your code must be able to print the sample output from the provided sample input. However, your code is run against multiple hidden test cases. Therefore, your code must pass these hidden test cases to solve the problem statement.

Time Limit: 1.0 sec(s) for each input file
Memory Limit: 256 MB
Source Limit: 1024 KB

 Scoring 

Score is assigned if any testcase passes.