310349: CF1818A. Politics

A. Politicstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 > N$), all members who disagreed leave the club.
• If more members disagree than agree ($Y < 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.

Input

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$.

Output

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

ExampleInput

5
2 2
++
+-
1 3
+-+
4 1
+
-
-
+
5 4
++++
+--+
++-+
+-++
++++
4 2
++
--
--
-+

Output

1
1
2
2
1

Note

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）共有n名成员，有k个观点需要依次讨论。在每次讨论中，成员们会表达他们对观点的支持或反对。定义Y为同意的成员数，N为不同意的成员数。每次讨论后，成员会根据以下标准离开俱乐部：

- 如果同意的成员多于不同意的（Y > N），所有不同意的成员离开俱乐部。
- 如果不同意的成员多于同意的（Y < N），所有同意的成员离开俱乐部。
- 如果平局（Y = N），所有成员离开俱乐部。

作为俱乐部主席，你的目标是留在俱乐部中，并最大化会议结束后剩余的成员数。你可以在会议开始前驱逐任何数量的成员（不包括你自己）。

确定会议结束后可以留在俱乐部的最大成员数，包括你自己。你不需要提供具体的驱逐策略，只需提供可以留下的最大成员数。确保会议结束后你自己也在俱乐部中。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 1000），表示测试用例的数量。
- 每个测试用例的第一行包含两个正整数n和k（1 ≤ n, k ≤ 100），分别表示成员数和讨论数。
- 接下来的n行，每行包含一个长度为k的字符串ti。字符串ti的第j个字符表示如果第i个成员在第j次讨论时在场，他对该观点是支持还是反对。"+"符号表示支持，"-"符号表示反对。

保证所有测试用例的n*k之和不超过5*10^4。

输出：
- 对于每个测试用例，输出会议结束后可以留在俱乐部的最大成员数，包括你自己。题目大意： 在一个辩论俱乐部中，包括你自己（成员1）共有n名成员，有k个观点需要依次讨论。在每次讨论中，成员们会表达他们对观点的支持或反对。定义Y为同意的成员数，N为不同意的成员数。每次讨论后，成员会根据以下标准离开俱乐部： - 如果同意的成员多于不同意的（Y > N），所有不同意的成员离开俱乐部。 - 如果不同意的成员多于同意的（Y < N），所有同意的成员离开俱乐部。 - 如果平局（Y = N），所有成员离开俱乐部。 作为俱乐部主席，你的目标是留在俱乐部中，并最大化会议结束后剩余的成员数。你可以在会议开始前驱逐任何数量的成员（不包括你自己）。 确定会议结束后可以留在俱乐部的最大成员数，包括你自己。你不需要提供具体的驱逐策略，只需提供可以留下的最大成员数。确保会议结束后你自己也在俱乐部中。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 1000），表示测试用例的数量。 - 每个测试用例的第一行包含两个正整数n和k（1 ≤ n, k ≤ 100），分别表示成员数和讨论数。 - 接下来的n行，每行包含一个长度为k的字符串ti。字符串ti的第j个字符表示如果第i个成员在第j次讨论时在场，他对该观点是支持还是反对。"+"符号表示支持，"-"符号表示反对。 保证所有测试用例的n*k之和不超过5*10^4。 输出： - 对于每个测试用例，输出会议结束后可以留在俱乐部的最大成员数，包括你自己。