Minimize the string

All submissions for this problem are available.
You are given n strings s_{1}, s_{2}, ..., s_{n}. Each of these strings consists only of letters 'a' and 'b', and the length of each string can be at most 2. In other words, the only allowed strings are "a", "b", "aa", "ab", "ba" and "bb".
Consider a permutation p = {p_{1}, p_{2}, ..., p_{n}} of the integers {1, 2, ..., n}. Using this permutation, you can obtain a new string S = s_{p1} + s_{p2} + ... + s_{pn}, where the operator + denotes concatenation of strings.
You can shorten the string S by performing the following operation any number of times: choose two consecutive equal characters and remove one of these characters from the string. For example, the string "aabb" can be shortened to "abb" or "aab" in one operation, and then optionally it could still be shortened to "ab".
You are allowed to choose any permutation p. Take the string S obtained using this permutation, and using any sequence of operations, minimize the string length. Find the minimum possible length of the string obtainable.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer n.
The second line of each test case contains n spaceseparated strings s_{1}, s_{2}, ..., s_{n}.
Output
For each test case, output a single line containing one integer corresponding to the minimum possible length of the shortened string.
Constraints
 1 ≤ T ≤ 10^{5}
 1 ≤ n ≤ 10^{5}
 sum of n over all test cases won't exceed 10^{6}
Example
Input 2 2 ba ab 4 a b a b Output 3 2
Explanation
Testcase 1:
You can consider the permutation (2, 1). Using this, you get the string S = s_{p1} + s_{p2} = ab + ba = abba. You can then take the two adjacent b's and remove one of them to get aba, whose length is 3. You cannot do any better, and hence the answer is 3.
Testcase 2:
You can consider the permutation (1, 3, 2, 4). Using this, you get the string S = s_{p1} + s_{p3} + s_{p2} + s_{p4} = a + a + b + b = aabb. You can then take the two adjacent b's and remove one of them to get aab. Then you can take the two adjacent a's and remove one of them to get ab. We end up with a length of 2, and you cannot do any better. Hence the answer is 2.
Author:  admin2 
Editorial  https://discuss.codechef.com/problems/MINSTR 
Tags  acm17chn, admin2, chn17rol, simple 
Date Added:  7122017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 