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

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

Входные данные

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

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

Выходные данные

Для каждого теста вывести последовательность строк в порядке от "наиболее отсортированной" до "наименее отсортированной". Если две или более строки равны при указанной сортировке, то выводить их следует в том же порядке в каком они поступали на вход.

Между ответами на соседние тесты следует выводить пустую строку.