Contents
Help Utkarsh solution codechef

For Solution
Click Here!
Utkarsh is a cool guy and had fun throughout the year. Now his exams are approaching and he hasn’t studied for them at all!
Utkarsh has to read several chapters for his exams, but he is smart and realized that he doesn’t actually need to read each and every one of them thoroughly. Several chapters share the same content, so he can skip some parts of some chapters to save time.
Each chapter is a nonempty string of lowercase characters. Utkarsh has to read NN distinct chapters for the exam, denoted by the set S={S1,S2,…,SN}S={S1,S2,…,SN}. He will read all NN chapters in some order.
Help Utkarsh solution codechef
For each chapter SiSi, he can skip reading some part of it by considering at most two other chapters that he has read already.
Formally, he has 33 options for the chapter Si:Si:

Suppose there exist two chapters Sj,Sk∈SSj,Sk∈S (jj can be equal to kk) that he has previously read, and three (possibly empty) strings of lowercase alphabets AA, BB, and CC such that Si=A+Sj+B+Sk+CSi=A+Sj+B+Sk+C (where ++ denotes string concatenation). Then he has to read only A+B+CA+B+C characters.

Suppose there exists a chapter Sj∈SSj∈S that he has previously read, along with two (possibly empty) strings AA and BB of lowercase alphabets such that Si=A+Sj+BSi=A+Sj+B. Then he has to read only A+BA+B characters.

Finally, he can also choose to read chapter SiSi completely, requiring SiSi characters.
Note that there is no forced hierarchy among the options, i.e, Utkarsh is free to choose how he reads SiSi chapter among all choices available to him.
Find the minimum amount of characters Utkarsh has to read in total if he chooses an optimal ordering of the chapters.
Input Format
Help Utkarsh solution codechef
 The first line of input contains a single integer TT, the number of test cases. The description of TT test cases follows.
 Each test case consists of N+1N+1 lines.
 The first line contains a single integer NN, the number of chapters.
 Each of the following NN lines contains a nonempty lowercase string.
Output Format
Help Utkarsh solution codechef
For each test case, print a single line containing one integer denoting the minimum number of characters Utkarsh has to read over all chapters.
Constraints
 1≤T≤1031≤T≤103
 1≤N≤1051≤N≤105
 1≤Si≤3⋅1051≤Si≤3⋅105
 Sum of SiSi over all test cases doesn’t exceed 2⋅1062⋅106.
Sample Input 1
Help Utkarsh solution codechef
3
5
a
aba
aabc
bc
c
2
aaa
bb
3
z
zz
zzz
Sample Output 1
5
5
1
Explanation
Help Utkarsh solution codechef
Test case 1:
Ukarsh reads the chapters in the following order :
 aa (reads 11 character)
 cc (reads 11 character)
 aba=a+b+aaba=a+b+a (first and last aa already read, reads 11 character)
 bc=b+cbc=b+c (cc already read, reads 11 character)
 aabc=a+a+bcaabc=a+a+bc (first aa and bcbc already read, reads 11 character)
Thus, 55 characters are read in total.
Test case 2:
Ukarsh reads the chapters in the following order :
 aaaaaa (reads 33 characters)
 bbbb (reads 22 characters)
Thus 55 characters are read in total.
Test case 3:
Ukarsh reads the chapters in the following order :
 zz (reads 11 character)
 zz=z+zzz=z+z (first and last zz already read,reads 00 characters)
 zzz=z+zzzzz=z+zz (zz and zzzz are already read,reads 00 characters)
Thus 11 character is read in total.

For Solution
Click Here!