Hacked Exam

There is an exam with Q true or false questions. The correct answer to each question is either T or F. Each student taking the exam selects either T or F for each question, and the student's score is the number of questions they answer correctly.

There are N students who have already taken this exam. For each of those students, you know the answers they gave to each question and their final score. Assuming that any sequence of answers that is consistent with all of those students' scores has the same probability of being the correct sequence of answers, you want to maximize your own expected score. Determine what that expected score is and how to answer the questions so that you achieve it.

The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains two integers N and Q: the number of students and the number of questions, respectively. Each of the next N lines contains a string Ai and an integer Si: the i-th student's answers and their score, respectively. The j-th character of Ai is either T or F, representing the answer the i-th student gave to the j-th question.

For each test case, output one line containing Case #x: y z/w, where x is the test case number (starting from 1), y is a string representing a sequence of answers that yields the maximum expected score (in the same format as the input), and z/w is the maximum expected score as an irreducible fraction (that is, w must be positive and of minimum possible value).

• 1 ≤ T ≤ 2021.
• The length of Ai = Q, for all i.
• Each character of Ai is an uppercase T or an uppercase F, for all i.
• 0 ≤ Si ≤ Q, for all i.
• There exists at least one sequence of correct answers consistent with the input.