Insertion Sort in Linked List

You are given an arbitrary linked list consisting of 'N' nodes having integer values. You need to perform insertion sort on the linked list and print the final list in sorted order.

In other words, you are given a singly linked list, you need to perform insertion sort on it.

Insertion Sort is a sorting algorithm that removes one element from the input data, finds the location it belongs within the sorted list and inserts it there. It repeats until no input elements remain.

Input Format

The first line of the input contains a single integer T, representing the number of test cases. 

The first line of each test case contains space-separated integers denoting the elements of the singly linked list terminated by -1.

Hence, -1 would never be a list element.

Output Format

For each test case, print space-separated integers denoting the elements of the linked list after performing the insertion sort.

Print the output of each test case in a separate line.

Note

You do not need to print anything. It has already been taken care of. Just implement the given function. Also, try to sort the linked list in-place.

Constraints

1 <= T <= 50
1 <= N <= 10^3
0 <= value of node < 10^9

Time Limit: 1sec