Even-Odd Sorting Challenge

You are given a series of test cases. For each test case, an integer N is provided denoting the number of elements in an array, followed by N integers. Your task is to rearrange the array so that all even numbers appear before all odd numbers while maintaining the relative order of the even and odd numbers.

The problem can be formalized as follows:

Given an array (A = [a_1, a_2, \dots, a_N]), produce an array (B) such that if (a_i) is even and (a_j) is odd, then (a_i) appears before (a_j) in (B). Moreover, the relative order among even numbers in (A) is preserved in (B) (and similarly for odd numbers).

For example, if the input array is [4, 3, 1, 2, 5], the expected output is [4, 2, 3, 1, 5].

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (T) indicating the number of test cases. For each test case, the first line contains an integer (N), denoting the number of elements in the array. The second line contains (N) space-separated integers representing the array.

outputFormat

For each test case, output the rearranged array on a single line with the numbers separated by a single space, ensuring that all even numbers come before all odd numbers while preserving the original order among evens and odds.## sample

1
5
4 3 1 2 5

4 2 3 1 5