在十九世纪，舞蹈是贵族在学校学习的最重要科目之一。舞会是结识新朋友的主要甚至唯一机会，无论是出于浪漫还是商业目的。然而，当时许多骑士在战争中阵亡。由于这些及其他原因，舞会上骑士短缺是一个相当普遍的问题。但这个问题有一个优雅的解决方案：一些舞蹈被修改为让一名骑士邀请两位女士共舞，而不是一位。新的舞蹈意味着除了通常的舞对之外，还出现了三元组舞蹈。

如今，有一些社群致力于舞蹈的复原，而骑士的数量通常仍然少于女士的数量。因此，现在也开始研究“女士-骑士-女士”的三元组舞蹈。Betty 是一位流行历史舞蹈社群的领袖。不幸的是，有些骑士和女士之间互不喜欢，不愿在同一个三元组中跳舞。Betty 非常细心，了解社群中所有此类不和。她现在需要一种方法来找出可以为舞蹈选择的三元组的最大数量 $t$。她甚至不需要知道骑士和女士之间具体的匹配方案，因为她喜欢给舞者出难题，说：“现在请组成 $t$ 个三元组。我知道这是可能的。”请帮助 Betty 找出最大的“女士-骑士-女士”双重匹配容量。

输入格式

输入的第一行包含测试用例的数量 $t$ ($1 \le t \le 20$)。接下来是 $t$ 个测试用例的描述。

对于每个测试用例，第一行包含骑士的数量 $n$ 和女士的数量 $m$ ($1 \le n, m; n + m \le 150$)。接下来的 $n$ 行包含每行 $m$ 个字符的字符串，字符为 '0' 或 '1'。第 $c$ 行第 $\ell$ 个位置的字符为 '1' 当且仅当女士 $\ell$ 可以与骑士 $c$ 组成一个三元组。单个输入中所有测试用例的 $n + m$ 之和不超过 $150$。

输出格式

对于每个测试用例，输出一行，包含三元组的最大数量 $t$。

样例

输入格式 1

2
2 3
111
111
3 4
0110
1100
0011

输出格式 1

1
2

输入格式 2

1
3 6
001100
111111
001100

输出格式 2

2

说明

在插图中，每一条线表示骑士可以与女士共舞。粗线表示骑士邀请女士共舞。