Little Party

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
A little party never killed nobody... After listening to this song many times Leha has decided to get together with his friends and have some fun again. But things are not as simple as you might think.
Leha has N friends and he already had M parties with them and for some reason all these events were not good. He guesses that sometimes guys can't get across with each other.
All his friends respect him and they always have come independently of their mood. And here is the problem: there is always some subset of his friends at the party that guys from these subset become angry.
Now Leha wants to analyze previous events and find some groups of his friends(maybe empty) with correspondent moods which usually lead to problems. He perfectly remembers their states during previous time. A friend could have come either with good mood(in this case we will denote it as an uppercase Latin letter) or with bad mood(in this case we will denote it as an lowercase Latin letter). The same letters(even if their cases differ) correspond to one friend and different letters correspond to different friends.
Let's consider an example: Leha has 3 friends and he had 3 parties with them with states AbC(friends A and C were in good mood, but B was in bad mood), Abc(A was in good mood, others were in bad), aBC(A was in bad mood, others were in good). During all these parties something had gone wrong. We can notice that when there is subset Ab(A was in good mood, but B was in bad mood) party is spoiled and the mood of friend C doesn't matter. We also have party with state aBC which gives us problems. We can't say anything special about other subsets(for example: here all parties are spoiled with subsets A, b but we don't have enough information to assume that these subsets are always bad)
So we have two subsets which if are presented guarantee us some problems: Ab and aBC. We will call them key subsets. Leha wants to find several key subsets with minimal total size that describe all problem parties. In the example enough key subsets with minimal total size are: Ab and aBC with total size of 5. He could also find subsets straightforwardly AbC, Abc, aBC but their total size would be 9, so he will choose the first option.
The idea of finding problem key subsets with minimal total size is good, but Leha doesn't like timeconsuming and boring tasks. He asks you to do this job for him.
Input
The first line of the input contains an integer T denoting the number of test cases. Each of the followingT test cases starts with two integer numbers N and M. M strings describing failed parties that already have been hold follow(one string per one line). Each string consists of N first Latin letters.
Output
For each test case, output a single line containing one integer  the minimal possible total size of key subsets.
Constraints
 1 ≤ T ≤ 120
 0 ≤ M ≤ 1000
Subtask 1 (23 points):
 1 ≤ N ≤ 3
Subtask 2 (77 points)
 1 ≤ N ≤ 5
Example
Input: 2 3 3 AbC Abc aBC 3 2 abc AbC Output: 5 6
Explanation
The first test case is explained in the problem statement.
In the second test case we can only take two given subsets and can't find anything less.
Author:  pavel1996 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/LPARTY 
Tags  april15, backtracking, bitmasking, hard, maths, pavel1996 
Date Added:  25022015 
Time Limit:  1.2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions