CF1818A Politics

在一个有着 $n$ 个成员的辩论俱乐部中（你是其中的第 $1$ 个成员），有 $k$ 个辩题即将被按顺序辩论。在每次辩论中，俱乐部的成员们会表达他们同意或者不同意这个辩题。我们假设有 $Y$ 个成员同意， $N$ 个成员不同意。在每次辩论之后，成员们会按照以下的规则退出俱乐部： + 如果同意的成员多于不同意的成员（ $Y > N$ ），那么所有不同意的成员会退出俱乐部； + 如果不同意的成员多于同意的成员（ $Y < N$ ），那么所有同意的成员会退出俱乐部； + 如果平局（ $Y = N$ ），那么所有成员都会退出俱乐部。 作为俱乐部的部长，你的目标是让自己待在俱乐部里，并且使辩论之后俱乐部里剩余的成员的数量最大化。在辩论开始之前，你已经得知了每一位成员对于各个辩题的意见，并且你可以在辩论开始之前开除任意数量的成员（不包括你自己）。 你需要求出辩论之后俱乐部里最多能剩下多少人（包括你自己）。你不需要输出开除的方案。请确保最后你自己还在俱乐部里。

每个测试点包含多组数据。输入数据的第一行包含数据组数 $t$ ( $1 \le t \le 100$ )。第二行及以下是测试数据。 每组测试数据的第一行包含两个正整数 $n$ 和 $k$ ( $1 \le n,k \le 100$ )，分别表示俱乐部内成员的个数和辩题的个数。 接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $k$ 的字符串 $t_i$ 。字符串 $t_i$ 中的第 $j$ 个字符（ $+$ 或 $-$ ）描述了第 $i$ 位成员对第 $j$ 个辩题的意见（如果这时候他/她还在俱乐部中）。“ $+$ ”代表同意，而“ $-$ ”代表不同意。 输入保证各组数据的 $n \sdot k$ 之和不超过 $5 \sdot 10^4$ 。

对于每组数据，输出辩论之后俱乐部里最多能剩下的人数。

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.