Tests are boring.
Peter hates tests.
One day he occasionally stumbled across a discarded lantern.
He took it home and guess what, a genie was inside and granted him a wish!
Peter is so excited. He made the wish that he will always get 100 on any test.
"So, genie, I want to get 100 in every tests from now on!", said Peter.
"What? That's such a boring wish! How about this: From now on, you will
able to decide the correct answer to a problem by yourself!"
"You mean, like, I can decide what is the right answer to each problem,
and there's no real correct answer that is given by the teacher?"
"Exactly!!! So?" asked the genie, with a promising grin.
"Okay! That will do." Peter agreed.
With a mysterious and meaningful smile the genie nodded and vanished.
Peter felt he is as smart as tmt514.
The next day Peter had history test.
He took the exam paper with confidence (that he will know all the answer),
but later discovered that, things didn't work out as he thought!
The tests actually look like:
"Okay, now that is a big joke," thought Peter.
"This looks nothing like history and how am I suppose to know the answer!!"
Now, please help Peter to find out in the best case, how much can he score?
The exam scoring scheme is simple, each problem he MUST choose exactly one
answer. If the statement corresponding to the answer he chooses is correct,
he gets one point.
(Yes, disregarding whether other options of that problem is also correct,
or whether he answers right to the problem referred to in the option.
That is, "The answer" in the option is simply "Peter's answer".)
The first line consists of an integer T, indicating the number of testcases.
Each testcase begins with two numbers N and K, indicating the number of problems in total and the number of options in a single problem, respectively.
Then there are N lines of specification for each problem. The i-th line describes the i-th problem (i starting from 1). The line starts with a number Pi denoting that this problem asks "What is the answer to prob. Pi". Then follows K uppercase letters describing the options (in the order of occurrence) as "The answer is x". See the sample input for more elaboration.
1 <= T <= 30
1 <= N <= 10000
1 <= K <= 26
All options will be valid (within the first K uppercase alphabets)
For each testcase, output a single number being the maximum score Peter can get.
3 4 4 2 ABCD 3 BCDA 1 BACD 1 BCAD 6 4 2 AADD 3 DBCA 4 ACBD 5 DBCA 6 ACBD 1 DBCA 1 3 1 BAB
4 5 0
In the first case, one of the best solution is to choose A, A, B, C for problem 1, 2, 3, 4 respectively.
For the second case, you must lose at least one point. (If you don't see how, consider different choices of problem A and eventually you must end up choosing something wrong.)
For the last case, there's no answer matching the right position, so you cannot get any point.
Migrated from old NTUJ.
kelvin
| No. | Testdata Range | Score |
|---|