We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Bit Manipulation
  4. What's Next?

What's Next?

Johnny is playing with a large binary number, . The number is so large that it needs to be compressed into an array of integers, , where the values in even indices () represent some number of consecutive bits and the values in odd indices () represent some number of consecutive bits in alternating substrings of .

For example, suppose we have array . represents , represents , represents , represents , and represents . The number of consecutive binary characters in the substring of corresponds to integer , as shown in this diagram:

When we assemble the sequential alternating sequences of 's and 's, we get .

We define setCount() to be the number of 's in a binary number, . Johnny wants to find a binary number, , that is the smallest binary number where setCount() = setCount(). He then wants to compress into an array of integers, (in the same way that integer array contains the compressed form of binary string ).

Johnny isn't sure how to solve the problem. Given array , find integer array and print its length on a new line. Then print the elements of array as a single line of space-separated integers.

Input Format

The first line contains a single positive integer, , denoting the number of test cases. Each of the subsequent lines describes a test case over lines:

  1. The first line contains a single positive integer, , denoting the length of array .
  2. The second line contains positive space-separated integers describing the respective elements in integer array (i.e., ).

Constraints

Subtasks

  • For a score, .
  • For a score, .

Output Format

For each test case, print the following lines:

  1. Print the length of integer array (the array representing the compressed form of binary integer ) on a new line.
  2. Print each element of as a single line of space-separated integers.

It is guaranteed that a solution exists.

Sample Input 0

1
5
4 1 3 2 4

Sample Output 0

7
4 1 3 1 1 1 3

Explanation 0

, which expands to . We then find setCount() . The smallest binary number which also has eleven 's is . This can be reduced to the integer array . This is demonstrated by the following figure:

Having found , we print its length () as our first line of output, followed by the space-separated elements in as our second line of output.