String Ka Khel Problem Statement

Ninja is creating a new game ‘String Ka Khel’ for his gaming shop. In this game, players are given ‘N’ strings. The objective is to find the maximum length of strings that can be formed by joining these ‘N’ strings. The condition for joining two strings is that the last character of the first string must match the last character of the second string. If the correct answer is found, the player wins Coding Ninja goodies.

Your task is to compute the maximum length of a string that can be formed following the given condition. If no combination is possible, return ‘0’. The strings consist only of the letters ‘B’ and ‘R’.

Example:

Input:

'RR', 'RB'

Output:

4

Explanation:

The string ‘RR’ can be combined with ‘RB’ because the last character of ‘RR’ (which is ‘R’) matches the first character of ‘RB’. However, ‘RB’ cannot be combined with ‘RR’ as the last character of ‘RB’ (which is ‘B’) does not match the first character of ‘RR’ (which is ‘R’). Hence, the maximum length is 4.

Input:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains an integer ‘N’ denoting the number of strings.
The second line of each test case contains ‘N’ space-separated strings.

Output:

For each test case, print a single line containing a single integer denoting the maximum length of the string which can be formed. If no two strings can be combined, print ‘0’.
The output for each test case will be printed in a separate line.

Constraints:

• 1 <= T <= 100
• 2 <= N <= 1000
• 1 <= |ST| <= 1000

Where ‘T’ represents the number of test cases, ‘N’ the number of strings, and ‘|ST|’ represents the length of each of the ‘N’ strings.

Time Limit: 1 second