#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define PB push_back
#define SZ(v) ((int)(v).size())
#define MP make_pair
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n) FORE(i,0,n)
#define REPSZ(i,v) REP(i,SZ(v))

typedef vector<int> VI;
typedef vector<VI> VVI;

typedef struct Node {
	vector<int> words;
	Node* next[26];
	int depth;
} Node;


int n,len;
vector<string> words;
char sortedwords[1000][21];

int nrnodes;
Node nodes[1+20*1000];
Node* root;
Node* createnode(int depth) {
	nodes[nrnodes].words.clear();
	memset(nodes[nrnodes].next,0,sizeof(nodes[nrnodes].next));
	nodes[nrnodes].depth=depth;
	return &nodes[nrnodes++];
}

VVI adj;
void addadj(int i,int j,Node *cur,char skip1,char skip2) {
	//sol
	if(j>=len&&skip1!='?'&&skip2!='?') REPSZ(k,cur->words) adj[i].PB(cur->words[k]);
	//skip sortedwords[i][j]
	if(j<len&&skip1=='?'&&sortedwords[i][j]>skip2) addadj(i,j+1,cur,sortedwords[i][j],skip2);
	//skip one in the trie
	if(skip2=='?') REP(k,26) if('a'+k>skip1&&cur->next[k]!=NULL) addadj(i,j,cur->next[k],skip1,'a'+k);
	//match
	if(j<len&&cur->next[sortedwords[i][j]-'a']!=NULL) addadj(i,j+1,cur->next[sortedwords[i][j]-'a'],skip1,skip2);
}

bool alldiff(char *a,char *b) {
	while(true) {
		if(*a=='\0'||*b=='\0') return true;
		if(*a<*b) ++a; else if(*b<*a) ++b; else return false;
	}
}

void run() {
	scanf("%d%d",&n,&len);
	words.clear(); REP(i,n) { char buff[21]; scanf("%s",buff); words.PB(buff); } sort(words.begin(),words.end());
	
	nrnodes=0;
	root=createnode(0);
	REP(i,n) {
		strcpy(sortedwords[i],words[i].c_str());
		sort(sortedwords[i],sortedwords[i]+strlen(sortedwords[i]));
		Node* cur=root;
		for(int j=0;sortedwords[i][j]!='\0';++j) {
			int k=sortedwords[i][j]-'a';
			if(cur->next[k]==NULL) cur->next[k]=createnode(cur->depth+1);
			cur=cur->next[k];
		}
		cur->words.PB(i);
	}
	
	adj=VVI(n);
	REP(i,n) { addadj(i,0,root,'?','?'); sort(adj[i].begin(),adj[i].end()); }
//	REP(i,n) { printf("%s:",words[i].c_str()); REPSZ(j,adj[i]) printf(" %s",words[adj[i][j]].c_str()); puts(""); }
	
	int best=INT_MAX; VI ret;
	REP(i,n) {
		VI prev(n,-1); 
		queue<int> q;
		int cur=0; prev[i]=-2; q.push(i);
		while(!q.empty()) {
			queue<int> nq;
			if(++cur>=best) goto done;
			while(!q.empty()) {
				int at=q.front(); q.pop();
				REPSZ(j,adj[at]) {
					int next=adj[at][j];
					if(prev[next]!=-1) continue;
//					printf("%s to %s in %d steps\n",words[i].c_str(),words[next].c_str(),cur);
					prev[next]=at;
					nq.push(next);
					if(alldiff(sortedwords[i],sortedwords[next])) {
						best=cur; ret.clear();
						for(int k=next;k!=i;k=prev[k]) ret.PB(k); ret.PB(i); reverse(ret.begin(),ret.end());
						goto done;
					}
				}
			}
			q=nq;
		}
done:	;
	}

	REPSZ(i,ret) { if(i!=0) printf(" "); printf("%s",words[ret[i]].c_str()); } puts("");
}

int main() {
	int n; scanf("%d",&n); FORE(i,1,n) run();
	return 0;
}
