Description

农夫 Shota 遇到了一点麻烦。他刚刚搬进自己新建的农舍，却发现房子的插座无法正确为他所有的设备充电。作为一位现代农夫，Shota 拥有大量的智能手机和笔记本电脑，甚至还为他最喜爱的奶牛 Wagyu 准备了一台平板电脑。总共，他拥有 $N$ 个不同的设备。

由于这些设备由不同厂商制造，规格也各不相同，因此每个设备都需要不同的电流格式来进行充电。同样地，房子中的每个插座也输出特定格式的电流。一个电流格式可以用一个长度为 $L$ 的仅包含 $0$ 和 $1$ 的字符串来表示。

Shota 希望能够同时为他所有的 $N$ 个设备充电。恰好，他新家的插座数量也正好是 $N$ 个。为了配置插座的电流格式，房子里设有一个总控制面板，带有 $L$ 个开关。第 $i$ 个开关用于翻转每个插座输出电流格式中的第 $i$ 位。例如，如果初始插座的电流格式如下：

插座 0：10
插座 1：01
插座 2：11

那么翻转第 2 个开关之后，插座的电流格式将变为：

插座 0：11
插座 1：00
插座 2：10

如果 Shota 的智能手机需要电流格式 "11" 充电，平板电脑需要 "10"，笔记本电脑需要 "00"，那么只需翻转第二个开关，他就可以非常开心地同时为所有设备充电了！

为了解决这个问题，Shota 雇佣了 Misaki 来帮忙。Misaki 测量了所有插座的电流格式，并发现它们都是不同的。现在你的任务是判断 Shota 是否可能通过翻转一些开关来让所有设备都能充电。如果可能，请计算出所需翻转的最少开关数，因为这些开关又大又重，Misaki 不想做无用功。

Input Format

输入的第一行是测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包括三行：

• 第一行包含两个用空格分隔的整数 $N$ 和 $L$。
• 第二行包含 $N$ 个长度为 $L$ 的字符串，表示初始插座的电流格式。
• 第三行也包含 $N$ 个长度为 $L$ 的字符串，表示 Shota 的每个设备所需的电流格式。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是使所有设备可以充电所需翻转的最少开关数量。如果无法做到，请输出字符串 "NOT POSSIBLE"（不含引号）。请注意，评测系统对大小写不敏感，但对拼写和其他格式非常严格；因此，虽然 "not possible" 会被判定为正确，但任何拼写错误的字符串都会被判定为错误。我们建议你直接复制粘贴字符串 "NOT POSSIBLE" 使用。

3
3 2
01 11 10
11 00 10
2 3
101 111
010 001
2 2
01 10
10 01

Case #1: 1
Case #2: NOT POSSIBLE
Case #3: 0

Hint

样例说明

在第一个测试用例中，Misaki 只需翻转第二个开关一次，插座电流格式变为：

插座 0：00
插座 1：10
插座 2：11

此时 Shota 可以使用插座 0 给设备 1 充电，插座 1 给设备 2 充电，插座 2 给设备 0 充电。这是所需翻转开关次数最少的一个解决方案。

限制条件

• $1 \leq T \leq 100$
• 初始状态下，任意两个插座的电流格式都不同
• 任意两个设备所需的电流格式也都不同

小数据集

• 时间限制：60 3 秒
• $1 \leq N \leq 10$
• $2 \leq L \leq 10$

大数据集

• 时间限制：120 5 秒
• $1 \leq N \leq 150$
• $10 \leq L \leq 40$

翻译由 ChatGPT-4o 完成。