T563585 Coin

小 M 和小 D 在玩游戏。 小 M 有个 $h$ 行 $w$ 列的棋盘，每个格子都包含了至多一枚硬币，硬币正面或者反面朝上。 小 M 和小 D 轮流操作，小 M 先手。每个人可以选择棋盘中没在之前被选择过的的一行或者一列，然后将所选的行或列上的硬币全部翻转，即正面变成反面，反面变成正面。 当所有硬币都正面朝上或者所有的行列都被选择，游戏结束。最后一次操作的玩家将会获得 1 分。如果当前局面所有的硬币都正面朝上，小 M 和小 D 都将获得 2 分的额外收益。 问两个人如果都按最优策略操作，即最大化自己的分数，那么小 M 最后的得分是多少。 保证每列至少有一个硬币，每行至少有一个反面朝上的硬币。

第一行包含一个整数 $T$ ，表示数据组数。 对于每组数据，第一行两个整数 $h, w$ ，表示棋盘大小。 接下来 $h$ 行，每行一个长度为 $w$ 的字符串，每个位置由为 $o, x, e$ 中一个。如果这个位置为 $e$ 表示没有硬币，如果是 $o$ 表示正面朝上，否则表示反面朝上。

共 $T$ 行，每行一个整数表示小 M 的分数。

# 数据范围 $10 \%$ 的数据，保证答案都为 0 或 1 。 $30 \%$ 的数据，保证答案不为 3 。 另外 $30 \%$ 的数据，保证 $h, w \leq 15$ 。 $100 \%$ 的数据，保证 $1 \leq T, h, w \leq 100$ 。