Given an integer array, try to sort it by Selection Sort Algorithm and Insertion Sort Algorithm. Also, you need to justify which algorithm performs better in this case. The performance is measured by the sum of comparison times and swap times, the lower, the better. It's guaranteed that performances are not the same in each test case.

The first line contains an integer T(1 ≤ T ≤ 10), representing the number of test cases.

For each test case, the first line will be an integer n (2 ≤ n ≤ 10^{3}) showing the length of array. Then there are n integers.

For each test case, the first line you need to output the sorted array in the ascending order.

The secondline, you need to output the better algorithm in this case.