Key to Knowledge

A while ago a class of students took an exam. Every question was true or false, and the questions were hard. Even afterward, with the textbook, the lecture notes and each other to work from, the students are not sure what all the correct answers were. They could ask the professor, but he is not the kind of person you would disturb with a question that gives away your ignorance. The students do at least remember exactly how they answered.

The professor has handed the exams back, and the results are not what anyone expected. He did not mark which answers were right or wrong. He wrote only the number of correct answers at the top of each paper. So what did the professor count as correct? Some of the grades are so far from what the students expected that a few of them suspect the professor miscounted.

Given the answers each student gave and the number of answers each student got right, work out the answer key that matches all of the results.

The first line holds one positive integer, the number of test cases, at most 100. Each test case is given as follows.

• One line with two space separated integers $n$ and $m$ ($1 \le n \le 12$, $1 \le m \le 30$): the number of students and the number of questions on the exam.
• $n$ lines, one per student. Each line holds $m$ digits, each digit either 0 or 1, the answers that student gave, where 0 means false and 1 means true. A single space follows, then an integer $c$ ($0 \le c \le m$), the number of questions that student got right.

Print one line per test case.

• If exactly one answer key accounts for all of the results, print that key as $m$ digits, each one either 0 or 1.
• Otherwise print how many answer keys account for all of the results, then a single space, then the word solutions. When no key works at all, the line reads 0 solutions.