{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003eYou are given \u003cb\u003en\u003c/b\u003e strings \u003cb\u003es\u003csub\u003e1\u003c/sub\u003e, s\u003csub\u003e2\u003c/sub\u003e, ..., s\u003csub\u003en\u003c/sub\u003e\u003c/b\u003e. Each of these strings consists only of letters \u0027a\u0027 and \u0027b\u0027, 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\".\u003c/p\u003e\r\n\r\n\u003cp\u003eConsider a permutation \u003cb\u003ep\u003c/b\u003e \u003d {\u003cb\u003ep\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003ep\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ..., \u003cb\u003ep\u003csub\u003en\u003c/sub\u003e\u003c/b\u003e} of the integers {1, 2, ..., \u003cb\u003en\u003c/b\u003e}. Using this permutation, you can obtain a new string \u003cb\u003eS \u003d s\u003csub\u003ep\u003csub\u003e1\u003c/sub\u003e\u003c/sub\u003e + s\u003csub\u003ep\u003csub\u003e2\u003c/sub\u003e\u003c/sub\u003e + ... + s\u003csub\u003ep\u003csub\u003en\u003c/sub\u003e\u003c/sub\u003e\u003c/b\u003e, where the operator + denotes concatenation of strings.\u003c/p\u003e\r\n\r\n\u003cp\u003eYou can shorten the string \u003cb\u003eS\u003c/b\u003e 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\".\u003c/p\u003e\r\n\r\n\u003cp\u003eYou are allowed to choose any permutation \u003cb\u003ep\u003c/b\u003e. Take the string \u003cb\u003eS\u003c/b\u003e obtained using this permutation, and using any sequence of operations, minimize the string length. Find the minimum possible length of the string obtainable.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of the input contains an integer \u003cb\u003eT\u003c/b\u003e denoting the number of test cases. The description of \u003cb\u003eT\u003c/b\u003e test cases follows.\u003c/p\u003e\r\n\u003cp\u003eThe first line of each test case contains an integer \u003cb\u003en\u003c/b\u003e.\u003c/p\u003e\r\n\u003cp\u003eThe second line of each test case contains \u003cb\u003en\u003c/b\u003e space-separated strings \u003cb\u003es\u003csub\u003e1\u003c/sub\u003e, s\u003csub\u003e2\u003c/sub\u003e, ..., s\u003csub\u003en\u003c/sub\u003e\u003c/b\u003e.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case, output a single line containing one integer corresponding to the minimum possible length of the shortened string.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e1 ≤ \u003cb\u003eT\u003c/b\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e\u003c/li\u003e\r\n\u003cli\u003e1 ≤ \u003cb\u003en\u003c/b\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e\u003c/li\u003e\r\n\u003cli\u003esum of \u003cb\u003en\u003c/b\u003e over all test cases won\u0027t exceed 10\u003csup\u003e6\u003c/sup\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\r\n\u003cb\u003eInput\u003c/b\u003e\r\n2\r\n2\r\nba ab\r\n4\r\na b a b\r\n\r\n\u003cb\u003eOutput\u003c/b\u003e\r\n3\r\n2\r\n\u003c/pre\u003e\r\n\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\u003cp\u003e\u003cb\u003eTestcase 1:\u003c/b\u003e\u003c/p\u003e \r\n\u003cp\u003eYou can consider the permutation (2, 1). Using this, you get the string \u003cb\u003eS\u003c/b\u003e \u003d \u003cb\u003es\u003csub\u003ep\u003csub\u003e1\u003c/sub\u003e\u003c/sub\u003e\u003c/b\u003e + \u003cb\u003es\u003csub\u003ep\u003csub\u003e2\u003c/sub\u003e\u003c/sub\u003e\u003c/b\u003e \u003d ab + ba \u003d abba. You can then take the two adjacent b\u0027s and remove one of them to get aba, whose length is 3. You cannot do any better, and hence the answer is 3.\u003c/p\u003e\r\n\r\n\u003cp\u003e\u003cb\u003eTestcase 2:\u003c/b\u003e\u003c/p\u003e \r\n\u003cp\u003eYou can consider the permutation (1, 3, 2, 4). Using this, you get the string \u003cb\u003eS\u003c/b\u003e \u003d \u003cb\u003es\u003csub\u003ep\u003csub\u003e1\u003c/sub\u003e\u003c/sub\u003e\u003c/b\u003e + \u003cb\u003es\u003csub\u003ep\u003csub\u003e3\u003c/sub\u003e\u003c/sub\u003e\u003c/b\u003e + \u003cb\u003es\u003csub\u003ep\u003csub\u003e2\u003c/sub\u003e\u003c/sub\u003e\u003c/b\u003e + \u003cb\u003es\u003csub\u003ep\u003csub\u003e4\u003c/sub\u003e\u003c/sub\u003e\u003c/b\u003e \u003d a + a + b + b \u003d aabb. You can then take the two adjacent b\u0027s and remove one of them to get aab. Then you can take the two adjacent a\u0027s 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.\u003c/p\u003e"}}]}