Move Evens to the Beginning

You are given an array of n integers. Your task is to rearrange the array so that all even numbers appear at the beginning and all odd numbers appear at the end, while preserving the relative order of the even numbers and the odd numbers.

In other words, if the given array is \(A = [a_1, a_2, \dots, a_n]\), you must output a new array \(B\) such that:

• All even numbers in \(A\) appear before any odd number.
• The even numbers in \(B\) are in the same order as they appear in \(A\).
• The odd numbers in \(B\) are in the same order as they appear in \(A\).

This is a simple but interesting problem suitable for beginners.

inputFormat

The first line contains a single integer \(T\) (\(1 \leq T \leq 100\)) representing the number of test cases. Each test case consists of two lines:

1. The first line contains an integer \(N\) (\(0 \leq N \leq 10^5\)) indicating the number of elements in the array.
2. The second line contains \(N\) space-separated integers.

It is guaranteed that the sum of \(N\) over all test cases does not exceed \(10^6\).

outputFormat

For each test case, output a single line containing the rearranged array. The numbers in the output should be space-separated. If the array is empty, output an empty line.

## sample

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

2 4 1 3
2 4 3 1 5
10 8 2 3 5 7

</p>