Reordering Warehouse Inventory

Problem Statement:

You are given the inventory records of one or more warehouses where each record is a list of integers representing the counts of different fruits. The task is to reorder each inventory list such that all even numbers come before all odd numbers, while maintaining the relative order among the even numbers and also among the odd numbers.

Formally, for a given list \(a_1, a_2, \ldots, a_n\), you need to produce a new list where:

• All items \(a_i\) such that \(a_i \equiv 0 \pmod{2}\) appear before items with \(a_i \equiv 1 \pmod{2}\).
• The relative order of even numbers remains unchanged.
• The relative order of odd numbers remains unchanged.

Input/Output: The input consists of multiple test cases. For each test case, the first line contains an integer \(N\) (the number of items in that warehouse), followed by a line containing \(N\) space-separated integers. The first line of the overall input gives the number of test cases. The output for each test case should be printed on a new line, with the reordered inventory numbers separated by a space.

Example:

Input:
2
5
3 8 6 1 4
4
7 3 2 5
Output:
8 6 4 3 1
2 7 3 5

</p>

inputFormat

The first line contains a single integer \(T\) denoting the number of test cases. Then for each test case, the first line contains an integer \(N\), the number of elements in the warehouse inventory. The next line contains \(N\) space-separated integers representing the counts of fruits.

Input is taken from standard input (stdin).

outputFormat

For each test case, output a single line containing the reordered inventory. The even numbers should come first followed by the odd numbers, with each item separated by a space.

Output is sent to standard output (stdout).

## sample

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

8 6 4 3 1
2 7 3 5

</p>