题目背景

翻译自 NERC 2018 B 题。

题目描述

你与一些好友一起举办了一个舞会！

在这个舞会上，有 $n$ 位男性和 $m$ 位女性，本来舞蹈的形式是一男一女跳的，但是由于男性紧缺，你并不能让所有女性都有一个男性舞伴，于是你发明了一种新的舞蹈形式：一个男性，搭配两个女舞伴。

当然，每个女性在挑选舞伴时，都会对那些男性舞伴做出评价，如果评价是 $1$，说明这位女性愿意和这位男性一起跳舞，只有当两位女性都愿意和那位男性跳舞时，才能成为一对舞伴。

你作为一个组织者，自然要为大家着想，你需要求出能凑出的最多的舞伴对数，每个舞伴不能重叠。

输入格式

第一行一个数 $t (1 \leq t \leq 20)$，表示数据组数。

接下来 $t$ 组数据，每组第一行两个整数 $n$ 和 $m$，此处我们保证 $1 \leq n,m$ 且 $n + m \leq 150$。

然后一个 $n \times m$ 的矩阵，$a_{i,j}$ 表示 $j$ 号女士是否愿意和 $i$ 号男士一起跳舞。

输出格式

对于每组测试数据，输出一行，表示最多能凑出的舞伴对数。

2
2 3
111
111
3 4
0110
1100
0011

1
2

1
3 6
001100
111111
001100

2

提示

数据保证 $1 \leq t \leq 20$，$1 \leq n, m$ 且 $n + m \leq 150$。

下图是对样例一和样例二的解释，其中加粗部分表示其中的一种可行方案。

样例一：

样例二：