Limits 3s, 1.0 GB

Mr. X and his best friend Mr. Potato Head are in the middle of a prison, the one and only prison of Byteland. They are here because of committing a horrible crime by sabotaging the world’s largest programming conference held in Wordland, a neighboring city of Byteland.
After finishing the horrible prison lunch it’s time for them to play their favorite game “Sequence Cracker”! They have been playing this game since the first day of their prison life and they are pretty obsessed with it. As they are very dangerous to deal with, no one ever tried to play with them. They just watch the game from a safe distance.
The game is a two player game. Each player has to play n levels to complete the game and they will play separately. A player can’t move to the next level without completing the current one. After completing all the levels the points will be summed up and compared. Winner will be the one with highest points. In each level a player will be given a binary sequence. To earn a point, (s)he needs to choose a subsequence of it. (S)he will be awarded a point if the picked subsequence is exactly same as the remaining subsequence. Here remaining subsequence means if the player removed his picked subsequence from the original sequence then the remaining part of the string will be considered as the remaining subsequence. Every time a player choose a new subsequence which is exactly same as the remaining subsequence, (s)he will be awarded a point. The level will be completed if there is no subsequences left to choose. Two chosen subsequences will be considered different if their positions in the original sequence differ by at-least one position.
Consider a binary sequence: “0001”. Here, subsequence with position {1, 2} is “00” and subsequence with position {2, 3} is also “00”. But their positions in original sequence differ by 1 position and they will be considered different.
Although Mr. X and Mr. Potato Head are best friends, none of them likes to lose! And if one of them lose by a huge margin then it will be a total disaster for the prison environment as both of them are crazy old Bytelanders.
The sequences have been generated by the game engine already. The warden seems interested about the result of the game but doesn’t want to happen anything ugly. That’s why he choose you to distribute the sequences into Mr. X and Mr. Potato Head so that at the end of the game the difference between the final scores remain as minimum as possible. He also forbid you to flash the distribution to avoid spoiling the intense of the game. So just tell him/her the minimum difference and (s)he will be happy as a shining star (or maybe not!).
You will be given 2n binary sequences. The length of each sequence |S| will be even. You need to distribute the sequences into Mr. X and Mr. Potato Head in such a way so that both of them get exactly n sequences and also it minimize the difference between the final scores. Please note that difference means absolute difference.

Input

Input will start with a positive integer T (T ≤ 5) denoting the number of test cases. Each test case will start with a positive integer n (1 ≤ n ≤ 15). Each of the following 2n lines will have a binary string S (2 ≤ |S| ≤ 30) consisting of only ‘1’ and ‘0’.

Output

For each test case just output the minimum difference.

Sample

InputOutput
1
1
1010
0000
4

Hint: There are only two sequences. One could possibly get 2 points from sequence 1010 and 6 points from 0000. So the minimum difference would be |6-2| = 4.

Submit

Login to submit.

Statistics

75% Solution Ratio
rumman13Earliest, May '18
nusuBotFastest, 0.1s
rumman13Lightest, 786 kB
AnachorShortest, 2437B
Toph uses cookies. By continuing you agree to our Cookie Policy.