Given a linked list, sort it using insertion sort.

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

Testing

Input Format

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

For each test case the input has two lines:

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

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
10
1 2 2 3 4 4 5 6 7 8

Expected Output

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

Constraints

1 <= T <= 100

1 <= n <= 500

1 <= element <= 500