Rearrange Alternately

Given an array arr of size N, containing positive and negative integers, rearrange the array such that every non-negative integer is followed by a negative integer and vice-versa.

Input:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case or query contains an integer 'N' representing the size of the array (arr).

The second line contains 'N' single space-separated integers, representing the elements in the array.

Output:

For each test case, output a rearranged array where every non-negative integer is followed by a negative integer and vice-versa.

Example:

Input:
array = {4, -9, -2, 6, -8}
Output: {-9, 4, -2, 6, -8}

Input:
array = {1, 2, 3, -5}
Output: {-5, 1, 2, 3}

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10^5
• Sum of N over all test cases does not exceed 10^5.
• -(10^9) <= arr[i] <= 10^9
• Time limit: 1 second

Note:

The number of positive integers and negative integers may not be equal. In such cases, add the extra integers at the end. For a single array, multiple solutions may be possible, just rearrange the array in any one possible way.