Reorder Array: Evens First, Odds Later

You are given an array of integers. Your task is to reorder the array such that all even numbers appear before all odd numbers while preserving their original relative order. In other words, for an array \(A\), you need to partition it into two segments: the first segment contains all elements \(x\) satisfying \(x \bmod 2 = 0\) and the second contains all elements with \(x \bmod 2 \neq 0\).

Example: For the array [1, 2, 3, 4, 5], the reordered array should be [2, 4, 1, 3, 5].

You need to handle multiple test cases. The input format is given below.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N1
a1 a2 ... aN1
N2
b1 b2 ... bN2
...
NT
...

Where:

• T: the number of test cases
• Ni: the number of elements in the i-th test case
• The next line contains Ni space-separated integers.

outputFormat

For each test case, output a single line containing the elements of the reordered array separated by a single space. The output is written to standard output (stdout).

1
4
2 4 6 8

2 4 6 8