Insertion Sort and Catalog Sorting

This problem requires you to implement the insertion sort algorithm and use it to sort lists of catalog numbers provided in multiple test cases. For each test case, you are given an integer N denoting the number of catalog numbers, followed by N integers. Your task is to sort these numbers in non-decreasing order using the insertion sort algorithm.

The insertion sort algorithm can be described by the recurrence:

$$O(n^2)$$

where n is the number of elements in the list. Although insertion sort has quadratic worst-case time complexity, it performs efficiently for small or nearly sorted inputs.

Please note that you must read the input from standard input (stdin) and write the output to standard output (stdout). Each test case's result should be output on a separate line with the sorted numbers separated by a single space.

inputFormat

The first line contains an integer T denoting the number of test cases. Each test case consists of two lines:

• The first line contains an integer N representing the number of catalog numbers.
• The second line contains N space-separated integers, which are the catalog numbers to be sorted.

All input is given via standard input (stdin).

outputFormat

For each test case, output a single line containing the sorted catalog numbers in non-decreasing order. The numbers should be output as space-separated values. All output should be printed to standard output (stdout).

## sample

2
5
12 4 5 3 8
3
1 2 3

3 4 5 8 12
1 2 3

</p>