Size tam sayılardan oluşan bir a_1, a_2, \ldots, a_n dizisi veriliyor.
Bir işlemde, a_i - a_j farkı ile bölünebilen iki farklı ve indisi seçip a_i ve a_j değerlerinin yerlerini değiştirebilirsiniz. İndislerin komşu olması gerekmez. İstediğiniz kadar, muhtemelen hiç, işlem yapabilirsiniz.
Elde edilebilecek sözlüksel olarak en küçük diziyi bulun.
Bir b_1, \ldots, b_n dizisi, farklı oldukları ilk konumunda b_i < c_i oluyorsa c_1, \ldots, c_n dizisinden sözlüksel olarak küçüktür. Elemanlar tam sayı olarak karşılaştırılır, yani örneğin -5 < 2.
İlk satırda bir tam sayı (1 \le t \le 10^4) — test durumlarının sayısı verilir.
Her test durumu iki satırdan oluşur. İlk satırda dizinin uzunluğu olan bir tam sayı (1 \le n \le 3 \cdot 10^5) verilir. İkinci satırda tam sayı a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) verilir.
Tüm test durumları boyunca değerlerinin toplamı 3 \cdot 10^5 değerini aşmaz.
Her test durumu için tam sayı içeren bir satır yazdırın: elde edilebilecek sözlüksel olarak en küçük dizi.
Örnek 1
Birinci test durumunda önce a_1 ile a_4, sonra a_2 ile a_3, sonra a_3 ile a_6, ardından a_4 ile a_5 yer değiştirilebilir. Dizi 2, -6, 0, 5, 8, 3 olur. Daha küçük bir dizi elde edilemeyeceği gösterilebilir.
İkinci test durumunda a_1 ile a_5, sonra da a_2 ile a_4 yer değiştirilebilir; bu da 4, -4, 7, -1, 10 dizisini verir.
Üçüncü test durumunda iki elemanın hiçbir farkı ile bölünemediğinden hiçbir işlem mümkün değildir ve dizi değişmez.