1.


/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 612 DNA Sorting
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=553
*
* @author Kratzer Kevin
* @version 1.0, 10/14/2009
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.780
*/

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main612 {

protected final BufferedReader input;
public static final int opAdd = 0;
public static final int opSub = 1;
public static final int opMul = 2;
public static final int opAmount = 3;

public Main612() {
input = new BufferedReader(new InputStreamReader(System.in));
}

void process() throws IOException {
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String line = input.readLine();
int datasets = Integer.parseInt(line);
for(int d=0; d < datasets; d++) {
input.readLine();
line = input.readLine();
int amount = Integer.parseInt(line.split(" ")[1]);
ArrayList<DNAEntry> list = new ArrayList<DNAEntry>();
for(int i=0;i < amount;i++) {
line = input.readLine();
int unsortedness = 0;
for(int j = 0; j < line.length(); j++) {
int curChar = line.charAt(j);
for(int k = j + 1; k < line.length(); k++) {
if(curChar > line.charAt(k)) {
unsortedness++;
}
}
}
list.add(new DNAEntry(line,unsortedness,i));
}
Collections.sort(list);
for(DNAEntry e: list) {
out.append(e.getContent());
out.append('\n');
}
if(d < datasets - 1)
out.append("\n");
}

out.flush();
}

private class DNAEntry implements Comparable<DNAEntry>{
private final String content;
private final int unsortedness;
private final int inputLine;
public DNAEntry(String content, int unsortedness, int inputLine) {
this.unsortedness = unsortedness;
this.content = content;
this.inputLine = inputLine;
}

public String getContent() {
return content;
}


public int getUnsortedness() {
return unsortedness;
}

public int getInputLine() {
return inputLine;
}

@Override
public int compareTo(DNAEntry o) {
if(this.unsortedness == o.unsortedness) {
return this.inputLine - o.inputLine;
}
return this.unsortedness - o.unsortedness;
}
}

public static void main(String... args) throws Exception {
new Main612().process();
}
}