Rearrange Inventory Array

You are given an inventory array of integers. Your task is to rearrange this array so that all odd numbers appear before all even numbers, while preserving the relative order of the odd and even numbers within their groups. The input consists of multiple test cases. For each test case, you will first receive an integer n (the number of elements in the array), followed by n space‐separated integers.

Mathematically, if the array is (A = [a_1, a_2, \dots, a_n]), then you need to produce an array (B) such that all odd numbers in (A) appear in (B) in the same order as in (A), followed by all even numbers, again in the same order as they appear in (A).

inputFormat

The first line contains a single integer (T) representing the number of test cases. Then, for each test case:

• The first line contains an integer (n), the number of elements in the array.
• The second line contains (n) space-separated integers representing the inventory array.

outputFormat

For each test case, output a single line with the rearranged array, where all odd numbers come first (preserving their original order) followed by all even numbers (preserving their original order).## sample

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

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