#include <cassert>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 100000;
int Tn, n, m, u[MAXN], ret, wn, cost[MAXN];
long long covers[MAXN], required, or_to_end[MAXN];
vector<string> a, current, descendants;
char lower_case (char a) {
	if (a >= 'a')
		return a;
	return a + 32;
}
string unite (string a, string b) {
	if (a.length() != b.length())
		return "-1";
	string ret = "";
	for(int i = 0; i < a.length(); i++)
		if (a[i] != b[i]) {
			if (lower_case(a[i]) != lower_case(b[i]))
				return "-1";
		} else
			ret += a[i];
	if (ret.length() != a.length() - 1)
		return "-1";
	else
		return ret;
}
bool contain (string what, string where) {
	what += "x";
	int j = 0;
	for(int i = 0; i < where.length(); i++)
		if (where[i] == what[j])
			++j;
	return (j + 1 == what.length());
}
inline int bitcount (long long k) {
	int ret = 0;
	while (k > 0) {
		++ret;
		k &= (k - 1);
	}
	return ret;
}
void backtrack (int pos, long long current_mask, int current_cost) {
	if (current_cost >= ret || (current_mask | or_to_end[pos]) != required)
		return;
	if (current_mask == required) {
		ret = current_cost;
		return ;
	}
	if (current_cost + cost[pos] < ret) {
		if ((current_mask | covers[pos]) != current_mask)
			backtrack(pos + 1, current_mask | covers[pos], current_cost + cost[pos]);
	}
	backtrack(pos + 1, current_mask, current_cost);
}
int main (int argc, char * const argv[]) {
	// freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin >> Tn;
	assert(1 <= Tn && Tn <= 120);
	while (Tn--) {
		cin >> n >> m;
		assert(1 <= n && n <= 5 && 0 <= m && m <= 1000);
		a.resize(m);
		for(int i = 0; i < m; i++)
			cin >> a[i];
		sort(a.begin(), a.end());
		a.resize(unique(a.begin(), a.end()) - a.begin());
		for(int i = 0; i < a.size(); i++)
			current.push_back(a[i]);
		sort(current.begin(), current.end());
		current.resize(unique(current.begin(), current.end()) - current.begin());
		vector<string> blind;
		blind.clear();
		while (current.size() > 0) {
			descendants.clear();
			for(int i = 0; i < current.size(); i++)
				u[i] = 0;
			// cerr << "CS: " << current.size() << endl;
			for(int i = 0; i < current.size(); i++)
				for(int j = i + 1; j < current.size(); j++) if (unite(current[i], current[j]) != "-1") {
					descendants.push_back(unite(current[i], current[j]));
					u[i] = u[j] = true;
					// break;
				}
			for(int i = 0; i < current.size(); i++)
				if (!u[i])
					blind.push_back(current[i]);
			sort(descendants.begin(), descendants.end());
			descendants.resize(unique(descendants.begin(), descendants.end()) - descendants.begin());
			current = descendants;
		}
		for(int i = 0; i < blind.size(); i++)
			covers[i] = 0;
		for(int i = 0; i < blind.size(); i++) {
			cost[i] = blind[i].size();
			for(int j = 0; j < a.size(); j++) if (contain(blind[i], a[j]))
				covers[i] += (1LL << (long long)j);
		}
		for(int i = 0; i < blind.size(); i++)
			for(int j = i + 1; j < blind.size(); j++)
				if (bitcount(covers[i]) > bitcount(covers[j])) {
					swap(covers[i], covers[j]);
					swap(cost[i], cost[j]);
				}
		wn = 0;
		for(int i = 0; i < blind.size(); i++) {
			bool fail = false;
			for(int j = 0; j < wn; j++) if ((covers[i] & covers[j]) == covers[i] && cost[i] >= cost[j]) {
				fail = true;
				break;
			}
			if (fail)
				continue;
			covers[wn] = covers[i];
			cost[wn] = cost[i];
			++wn;
		}
		or_to_end[wn] = 0;
		for(int i = wn - 1; i >= 0; i--)
			or_to_end[i] = or_to_end[i + 1] | covers[i];
		cerr << "wn = " << wn << endl;
		ret = 1000000000;
		required = (1LL << (long long)a.size()) - 1LL;
		backtrack(0, 0, 0);
		cout << ret << endl;
	}
	return 0;
}