Nasser's Concatenation#12479
Nasser has four strings , , , and , each of length , consisting only of characters 'a' and 'b'.
He can concatenate these four strings in any order to form a single string of length . After choosing the concatenation order, Nasser wants to find the maximum possible length of a substring of that consists of a single repeated character (all 'a's or all 'b's).
In other words, for each possible permutation of the four strings, compute the longest contiguous substring where all characters are the same, and then output the maximum such length over all possible concatenation orders.
Each test contains multiple test cases. The first line contains a single integer (1 \le t \le 10^4) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer (1 \le n \le 2 \cdot 10^5) — the length of each string.
The second line of each test case contains a string of length .
The third line of each test case contains a string of length .
The fourth line of each test case contains a string of length .
The fifth line of each test case contains a string of length .
All strings consist only of characters 'a' and 'b'.
It is guaranteed that the sum of over all test cases does not exceed 2 \cdot 10^5.
For each test case, print a single integer — the maximum possible length of a uniform substring (all 'a's or all 'b's) that can be obtained by concatenating the four strings in some order.
Example 1
Subtask ( points) : (1 \le \sum n \le 500)
Subtask ( points) : No additional constraints.