Задано масив цілих чисел a_1, a_2, \ldots, a_n.
За одну операцію можна вибрати два різні індекси та такі, що a_i - a_j ділиться на , і поміняти місцями значення a_i та a_j. Індекси не обов'язково сусідні. Можна виконати будь-яку кількість операцій, зокрема жодної.
Знайдіть лексикографічно найменший масив, який можна отримати.
Масив b_1, \ldots, b_n лексикографічно менший за масив c_1, \ldots, c_n, якщо b_i < c_i на першій позиції , де вони відрізняються. Елементи порівнюються як цілі числа, тож, наприклад, -5 < 2.
Перший рядок містить одне ціле число (1 \le t \le 10^4) — кількість тестових випадків.
Кожен тестовий випадок складається з двох рядків. Перший рядок містить ціле число (1 \le n \le 3 \cdot 10^5) — довжину масиву. Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9).
Сума за всіма тестовими випадками не перевищує 3 \cdot 10^5.
Для кожного тестового випадку виведіть один рядок з цілими числами: лексикографічно найменший масив, який можна отримати.
Приклад 1
У першому тестовому випадку можна поміняти місцями a_1 і a_4, потім a_2 і a_3, потім a_3 і a_6, а потім a_4 і a_5. Масив стане 2, -6, 0, 5, 8, 3. Можна показати, що меншого масиву отримати неможливо.
У другому тестовому випадку можна поміняти місцями a_1 і a_5, а потім a_2 і a_4 й отримати 4, -4, 7, -1, 10.
У третьому тестовому випадку жодна різниця двох елементів не ділиться на , тому жодна операція неможлива і масив не змінюється.