Reorder List by Parity

You are given a list of integers. The goal is to reorder the list so that all even numbers appear before all odd numbers while preserving the relative order of even numbers among themselves and odd numbers among themselves.

In other words, for each number \(x\) in the list, if \(x \bmod 2 = 0\) then \(x\) is even, otherwise it is odd. Your task is to segregate the list into two parts: the first containing all even numbers in the order they appeared, and the second containing all odd numbers in their original order.

Example:

Input:  5
        1 2 3 4 5
Output: 2 4 1 3 5

inputFormat

The first line of the input contains a single integer \(T\), the number of test cases. Each test case is described as follows:

• The first line of the test case contains an integer \(N\) denoting the number of elements in the list.
• The second line contains \(N\) space-separated integers representing the list elements.

outputFormat

For each test case, output a single line containing the reordered list. The numbers should be space-separated.

## sample

3
5
1 2 3 4 5
4
10 21 30 41
3
7 9 11

2 4 1 3 5
10 30 21 41
7 9 11

</p>