在一个拥有 $$$n$$$ 成员(包括你自己(成员 $$$1$$$))的辩论俱乐部中,有 $$$k$$$ 个观点需要按顺序讨论。在每次讨论中,成员都会表达他们同意或不同意的观点。我们将 $$$Y$$$ 定义为同意的成员数量,将 $$$N$$$ 定义为不同意的成员数量。每次讨论后,会员根据以下标准离开俱乐部:
- 如果同意的成员多于不同意的成员 ($$$Y > N$$$),则所有不同意的成员离开俱乐部。
- 如果不同意的成员多于同意的成员 ($$$Y < N$$$),则所有同意的成员都会离开俱乐部。
- 如果平局 ($$$Y = N$$$),则所有成员离开俱乐部。
作为俱乐部主席,您的目标是留在俱乐部并最大限度地增加会议后剩余的会员数量。在会议开始之前,您可以了解每个成员对所有 $$$k$$$ 意见的立场,并且您可以在会议开始之前驱逐任意数量的成员(不包括您自己)。
确定会议结束后可以留在俱乐部的会员(包括您自己)的最大人数。您无需提供具体的驱逐策略,只需提供可以留下的最大成员数即可。确保会议结束后您也留在俱乐部。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个正整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 100$$$) — 成员数量和讨论数量。
以下 $$$n$$$ 行中的第 $$$i$$$ 行包含长度为 $$$k$$$ 的字符串 $$$t_i$$$。字符串 $$$t_i$$$ 中的第 $$$j$$$ 个字符指示第 $$$i$$$ 个成员是否同意或不同意第 $$$j$$$ 个意见(如果他们在该讨论期间在场)。 “+”号表示会员同意,“-”号表示会员不同意。
保证所有测试用例的 $$$n \cdot k$$$ 总和不超过 $$$5 \cdot 10^4$$$。
输出
对于每个测试用例,输出会议结束后可以留在俱乐部的成员(包括您自己)的最大数量。
示例
输入 #1
5 2 2 ++ +- 1 3 +-+ 4 1 + - - + 5 4 ++++ +--+ ++-+ +-++ ++++ 4 2 ++ -- -- -+
输出 #1
1 1 2 2 1
注意
为了方便起见,我们将根据实际参加会议的人员(即未被开除)而不是被开除的人员来分析示例。
示例 1:
只有第一个成员可以参加会议,否则在讨论第二个意见后,两个成员都会离开。
示例 2:
只有一名成员出席会议并留到最后。
示例 3:
俱乐部有 $$$4$$$ 会员,会议期间只会讨论一种意见。让我们根据会议参与者来分析可能的结果:
- 如果只有第一位成员参加,那么他们将是会议结束后剩下的唯一成员。
- 如果第一个成员与第二个或第三个成员一起参加,他们将在讨论中打平,导致他们双双离开。
- 如果第一个成员与第二个和第三个成员一起参加,则第一个成员将成为少数成员,并将在讨论后离开,这与声明相矛盾。
- 如果第一名和第四名成员出席,他们将在讨论过程中达成一致,并且两人都会留到最后。
- 如果第一、第二和第四位成员参加,则第二位成员在讨论过程中将成为少数,最后只剩下第一和第四位成员。如果第二个成员被第三个成员替换,也会发生同样的情况。
- 如果四名成员都参加,讨论过程中就会出现平局,导致所有人离开。
会议结束后剩余成员的最大人数为$$$2$$$。
示例 4:
俱乐部有$$$5$$$会员,会议期间将讨论$$$4$$$意见。
实现最大成员人数的一种方法是只有第一、第三和第五名成员参加会议。在这种情况下,他们在前两次讨论中都同意,之后在第三次讨论中第三个成员处于少数。然后,第一名和第五名成员在最后一次讨论中达成一致,这两名成员留到会议结束。
示例 5:
俱乐部有 $$$4$$$ 会员,将讨论 $$$2$$$ 意见。
如果前三名成员出席会议,则第一位成员在第一次讨论中将属于少数派,并将离开俱乐部。之后,第二名和第三名成员均不同意第二个意见,并留至会议结束。这样,会议结束后就会剩下2名成员,但这是一个无效的结果,因为它迫使第一个成员离开。因此,如果只有第一位成员出席会议,则达到 1 名成员的最大人数。