CF1818A.Politics

In a debate club with $n$ members, including yourself (member $1$), there are $k$ opinions to be discussed in sequence. During each discussion, members express their agreement or disagreement with the opinion. Let's define $Y$ as the number of members who agree and $N$ as the number of members who disagree. After each discussion, members leave the club based on the following criteria:

• If more members agree than disagree ($Y \gt N$), all members who disagreed leave the club.
• If more members disagree than agree ($Y \lt N$), all members who agreed leave the club.
• If there is a tie ($Y = N$), all members leave the club.

As the club president, your goal is to stay in the club and maximize the number of members remaining after the meeting. You have access to each member's stance on all $k$ opinions before the meeting starts, and you can expel any number of members (excluding yourself) before the meeting begins.

Determine the maximum number of members, including yourself, who can remain in the club after the meeting. You don't need to provide the specific expulsion strategy but only the maximum number of members that can stay. Ensure that you remain in the club after the meeting as well.

在一个有 $n$ 名成员（包括你自己，即第 $1$ 号成员）的辩论俱乐部中，将依次讨论 $k$ 个观点。在每次讨论中，成员需表明自己对该观点是同意还是反对。定义 $Y$ 为表示同意的成员人数，$N$ 为表示反对的成员人数。每次讨论结束后，成员将依据以下规则离开俱乐部：

• 若同意者多于反对者（$Y \gt N$），所有表示反对的成员离开俱乐部；
• 若反对者多于同意者（$Y \lt N$），所有表示同意的成员离开俱乐部；
• 若双方人数相等（$Y = N$），所有成员均离开俱乐部。

作为俱乐部主席，你的目标是在会议结束后仍留在俱乐部中，并使最终留在俱乐部中的成员人数最大化。你可在会议开始前获知每位成员对全部 $k$ 个观点的立场，并且你可以在会议开始前任意驱逐若干名成员（但不能驱逐你自己）。

请确定会议结束后最多能有多少名成员（包括你自己）留在俱乐部中。你无需给出具体的驱逐策略，只需输出能够留下的最大成员人数。注意：你本人必须在会议结束后仍留在俱乐部中。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains two positive integers $n$ and $k$ ($1 \le n, k \le 100$) — the number of members and the number of discussions.

The $i$-th of the following $n$ lines contains a string $t_i$ of length $k$. The $j$-th character in the string $t_i$ indicates whether the $i$-th member agrees or disagrees with the $j$-th opinion if they are present during that discussion. A "+" symbol means the member agrees, while a "-" symbol means the member disagrees.

It is guaranteed that the sum of $n \cdot k$ over all test cases does not exceed $5 \cdot 10^4$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个正整数 $n$ 和 $k$（$1 \le n, k \le 100$）——分别表示成员数量和讨论次数。

接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $k$ 的字符串 $t_i$。该字符串中第 $j$ 个字符表示第 $i$ 位成员在第 $j$ 次讨论中（若其出席该次讨论）对第 $j$ 个观点的赞同或反对态度："+" 表示赞同，"-" 表示反对。

保证所有测试用例中 $n \cdot k$ 的总和不超过 $5 \cdot 10^4$。

For each test case, output the maximum number of members, including yourself, who can remain in the club after the meeting.

对于每个测试用例，输出会议结束后（包括你自己在内）仍可留在俱乐部中的最多成员人数。

For convenience, we will analyze the examples based on who actually attended the meeting (i. e. was not expelled) rather than who was expelled.

Example 1:

Only the first member could have attended the meeting, otherwise both members would have left after the second opinion is discussed.

Example 2:

There is only a single member that attends the meeting and stays till the end.

Example 3:

The club has $4$ members and only one opinion will be discussed during the meeting. Let's analyze the possible outcomes based on the participants in the meeting:

• If only the first member attends, they'll be the only one left after the meeting.
• If the first member attends with the second or third member, they will be a tie in the discussion, making them both leave.
• If the first member attends with the second and third members, the first member will be in the minority and will leave after the discussion, which contradicts the statement.
• If the first and fourth members attend, they will agree during the discussion and both remain till the end.
• If the first, second, and fourth members attend, the second member will be in the minority during the discussion, and only the first and fourth members will remain at the end. The same happens if the second member is replaced by the third member.
• If all four members attend, there will be a tie during the discussion, making everyone leave.

The maximum number of members remaining after the meeting is $2$.

Example 4:

The club has $5$ members and $4$ opinions will be discussed during the meeting.

One way to achieve the maximum number of members is if only the first, third, and fifth members attend the meeting. In this case, they all agree during the first two discussions, after which the third member is in the minority during the third discussion. Then, the first and fifth members agree in the last discussion, and those two members stay till the end of the meeting.

Example 5:

The club has $4$ members and $2$ opinions will be discussed.

If the first three members attend the meeting, the first member will be in the minority during the first discussion and will leave the club. After that, the second and third members will both disagree with the second opinion, and they both will stay till the end of the meeting. In this way, there will be 2 members left after the meeting, but it is an invalid outcome, as it forces the first member to leave. Therefore, the maximum number of 1 member is achieved if only the first member attends the meeting.

为方便起见，我们将基于实际出席会议（即未被驱逐）的成员来分析示例，而非基于被驱逐的成员。

示例 1：

只有第一位成员可能出席了会议；否则，在讨论第二项意见后，两位成员都将离开。

示例 2：

仅有一位成员出席了会议，并一直留至会议结束。

示例 3：

该俱乐部有 $4$ 位成员，会议期间仅讨论一项意见。我们根据出席会议的成员分析可能的结果：

• 若仅有第一位成员出席，则会议结束后仅剩其一人；
• 若第一位成员与第二位或第三位成员共同出席，则在讨论中将形成平局，导致二人均离开；
• 若第一位、第二位和第三位成员共同出席，则第一位成员将在讨论中处于少数，从而在讨论后离开，这与题设矛盾；
• 若第一位和第四位成员出席，则他们在讨论中意见一致，两人均留至会议结束；
• 若第一位、第二位和第四位成员出席，则第二位成员在讨论中处于少数，最终仅第一位和第四位成员留下；若将第二位成员替换为第三位成员，结果相同；
• 若全部四位成员均出席，则讨论中将出现平局，导致所有人离开。

会议结束后剩余成员的最大数量为 $2$。

示例 4：

该俱乐部有 $5$ 位成员，会议期间将讨论 $4$ 项意见。

一种实现成员数最大化的方案是：仅有第一位、第三位和第五位成员出席会议。此时，他们在前两次讨论中均意见一致；在第三次讨论中，第三位成员处于少数并离开；在最后一次讨论中，第一位和第五位成员意见一致，二人均留至会议结束。

示例 5：

该俱乐部有 $4$ 位成员，会议期间将讨论 $2$ 项意见。

若前三位成员出席了会议，则第一位成员将在第一次讨论中处于少数并被驱逐出俱乐部。此后，第二位和第三位成员均不同意第二项意见，因而二人均留至会议结束。如此，会议结束后将剩下 2 位成员；但该结果无效，因其强制第一位成员离开。因此，当仅有第一位成员出席会议时，可实现最多 1 位成员留下的有效结果。