Однією з мір "невпорядкованості" у послідовності є кількість пар елементів, які знаходяться у неправильному порядку по відношенню один до одного. Наприклад, у послідовності літер "DAABEC", ця міра рівна 5, оскільки D більше чотирьох літер праворуч, а Е більше однієї літери праворуч. Цією мірою є кількість інверсій у послідовності. Послідовність "AACEDGG" має лише одну інверсію (E і D) - вона майже відсортована, у той час як послідовність "ZWQM" має 6 інверсій (вона повністю невідсортована).

Вам необхідно відсортувати послідовність ДНК рядків (вони містять лише чотири літери A, C, G, Т). Проте сортування слід проводити не у алфавітному порядку, а у порядку "впорядкованості", від "самих відсортованих" до "найменш відсортованих". Усі рядки мають однакову довжину.

Вхідні дані

Перший рядок містить ціле число t, за яким йде пустий рядок і t тестів. Між сусідніми тестами знаходиться пустий рядок.

Перший рядок кожного тесту містить два цілих числа: довжину вхідних рядків n (0 < n ≤ 50) та кількість рядків m (0 < m ≤ 100). Далі йдуть m рядків, кожен з яких має довжину n.

Вихідні дані

Для кожного тесту вивести послідовність рядків у порядку від "найбільш відсортованої" до "найменш відсортованої". Якщо два або більше рядків рівні при вказаному сортуванні, то виводити їх сліду у тому ж порядку у якому вони поступали на вхід.

Між відповідями сусідні тести слід виводити пусти рядок.