SP1462 BARB - Barbarians

在一个未知的岛屿上，住着 $N$ 个野蛮人。岛上有 $M$ 个洞穴，这些洞穴按顺时针方向编号为 $1, 2, \ldots, M$。当我们发现这个岛的时候，野蛮人分别居住在编号为 $C_1, C_2, \ldots, C_N$ 的不同洞穴中。每年，野蛮人都会离开自己的洞穴，沿着道路往前走 $P_i$ 个洞穴，然后进入那一个洞穴。每个野蛮人的寿命为 $L_i$ 年，达到寿命年限后，第 $i$ 个野蛮人就会去世。 我们惊讶地发现，在任何一年内，没有任何两个野蛮人住在同一个洞穴中，这就避免了所有可能的冲突。我们希望找到岛上最少需要的洞穴数量。 需注意，该问题对代码长度和执行时间有一定限制。

第一行输入一个整数 $T$，表示有多少组测试数据。然后是 $T$ 组测试数据。 每组数据第一行包含一个整数 $N$（$N \leq 15$）。接下来的 $N$ 行中，每行包含三个整数 $C_i$（$1 \leq C_i \leq 100$）、$P_i$（$1 \leq P_i \leq 100$）和 $L_i$（$1 \leq L_i \leq 1,000,000$）。

对每组测试数据，输出一个整数 $M$，表示最少需要的洞穴数量。可以假设 $M \leq 1,000,000$。

- 测试用例数 $1 \leq T \leq 10$。 - 野蛮人数 $1 \leq N \leq 15$。 - 起始洞穴编号 $C_i$：$1 \leq C_i \leq 100$。 - 行进洞穴数 $P_i$：$1 \leq P_i \leq 100$。 - 野蛮人寿命 $L_i$：$1 \leq L_i \leq 1,000,000$。 - 洞穴总数 $M \leq 1,000,000$。 **本翻译由 AI 自动生成**