P13247 [GCJ 2014 #1A] Charging Chaos

农夫 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 不想做无用功。

输入的第一行是测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包括三行： - 第一行包含两个用空格分隔的整数 $N$ 和 $L$。 - 第二行包含 $N$ 个长度为 $L$ 的字符串，表示初始插座的电流格式。 - 第三行也包含 $N$ 个长度为 $L$ 的字符串，表示 Shota 的每个设备所需的电流格式。

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

**样例说明** 在第一个测试用例中，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 完成。