Rearrange Array by Even-Odd Partition

You are given an array of integers. Your task is to rearrange the array so that all even numbers appear before all odd numbers while preserving the relative order among even numbers and odd numbers separately.

In other words, if we denote an array by \(A = [a_1, a_2, \ldots, a_N]\), you need to compute a new ordering of the array where every even number in \(A\) appears before any odd number in \(A\), while the relative order of the even numbers remains the same as in the original array, and similarly for the odd numbers.

Example:

Input:  [4, 3, 1, 2, 7, 8]
Output: [4, 2, 8, 3, 1, 7]

Note: The input will consist of multiple test cases. For each test case, you will receive an integer \(N\) representing the number of elements, followed by \(N\) space‐separated integers.

inputFormat

The input is read from stdin and consists of multiple test cases. The first line contains a single integer \(T\) indicating the number of test cases. Each test case is then given in the following format:

• The first line of each test case contains an integer \(N\) (the size of the array).
• The second line contains \(N\) space-separated integers.

For example:

2
6
4 3 1 2 7 8
5
2 4 6 1 3

outputFormat

For each test case, output a single line containing the rearranged array where even numbers come first (preserving their original order) followed by odd numbers (also preserving their order). Each number should be separated by a space. The output for each test case should be written to stdout.

## sample

2
6
4 3 1 2 7 8
5
2 4 6 1 3

4 2 8 3 1 7
2 4 6 1 3

</p>