题目描述

在一个有着 $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$ 。

输出格式

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

样例

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

1
1
2
2
1