Given a linked list and a key, partition it such that all nodes with values less than key are before it and all nodes with values greater than key are after it.

The relative order of the numbers in each of the partition should be maintained.

Linked list: 1 → 6 → 2 → 4 → 3 → 5 → 2 → 8 → 4 → 7
key: 5
Result: 1 → 2 → 4 → 3 → 2 → 4 → 5 → 6 → 8 → 7

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of independent test cases.

For each test case the input has three lines:

• An integer ‘n’ denoting the length of the linked list.
• n space-separated integers denoting elements of the linked list.
• An integer 'key' denoting the pivot element.

Output Format

For each test case, a line containing ‘n’ space-separated integers denoting the resultant linked list elements.

Sample Input

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

Expected Output

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

Constraints

1 <= T <= 1000

1 <= n <= 1000

1 <= key <= 1000

1 <= element <= 1000