You are given an array a_1, a_2, \ldots, a_n of integers.
In one operation you may choose two different indices and such that a_i - a_j is divisible by and swap the values a_i and a_j. The indices do not have to be adjacent. You may perform any number of operations, possibly zero.
Find the lexicographically smallest array that can be obtained.
An array b_1, \ldots, b_n is lexicographically smaller than an array c_1, \ldots, c_n if b_i < c_i at the first position where they differ. The elements are compared as integers, so, for example, -5 < 2.
The first line contains a single integer (1 \le t \le 10^4) — the number of test cases.
Each test case consists of two lines. The first line contains an integer (1 \le n \le 3 \cdot 10^5) — the length of the array. The second line contains integers a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9).
The sum of over all test cases does not exceed 3 \cdot 10^5.
For each test case print one line with integers: the lexicographically smallest array that can be obtained.
Example 1
In the first test case one can swap a_1 and a_4, then a_2 and a_3, then a_3 and a_6, and then a_4 and a_5. The array becomes 2, -6, 0, 5, 8, 3. It can be shown that no smaller array can be obtained.
In the second test case one can swap a_1 and a_5, and then a_2 and a_4, which gives 4, -4, 7, -1, 10.
In the third test case no difference of two elements is divisible by , so no operation is possible and the array does not change.