Description

在游戏 "Duck, Duck, Goose" 中，除一名玩家外，其余玩家坐在地板上围成一个圈。剩下的玩家绕着圈走，依次称呼每个坐着的玩家为 "duck"，直到他们选择一名坐着的玩家，轻拍其头部并称其为 "goose"。此时，"goose" 会追逐选择者，而我们对游戏的兴趣就此消失。

在新游戏 "Duck, Duck, Geese" 中，行走的玩家改为选择一个连续的、至少包含两名（但非全部）坐着的玩家作为 "geese"！此外，每名坐着的玩家都戴着一顶帽子。每顶帽子是 $\mathbf{C}$ 种可能颜色中的一种，编号为 1 到 $\mathbf{C}$。

对于每种颜色 $i$，被选为 "geese" 的玩家中戴颜色 $i$ 帽子的数量必须为 0，或在 $\mathbf{A}_i$ 和 $\mathbf{B}_i$ 之间（含端点）。

你能帮忙计算满足这些要求的选择数量吗？如果某个玩家在一个选择中被包含而在另一个选择中未被包含，则这两个选择被视为不同。

Input Format

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含两个整数 $\mathbf{N}$ 和 $\mathbf{C}$：分别表示坐着的玩家数量和帽子颜色数量。接下来是 $\mathbf{C}$ 行，第 $i$ 行包含两个整数 $\mathbf{A}_i$ 和 $\mathbf{B}_i$，如上所述。每个测试用例的最后一行包含 $\mathbf{N}$ 个整数 $\mathbf{P}_1, \mathbf{P}_2, \ldots, \mathbf{P}_\mathbf{N}$，表示按顺时针方向（从任意一个玩家开始）的第 $j$ 名坐着的玩家戴的帽子颜色为 $\mathbf{P}_j$。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足所有颜色要求的、连续坐着的玩家集合的数量（集合大小至少为 2，最多为 $\mathbf{N} - 1$）。

3
3 2
1 1
1 1
1 1 2
5 2
1 1
1 2
1 2 1 2 2
3 3
1 2
1 2
2 2
1 1 3

Case #1: 2
Case #2: 9
Case #3: 1

Hint

样例解释

在样例 #1 中，被选为 "geese" 的玩家总数必须为 2。只有三种选择 2 名玩家的方式。可能的帽子颜色配置为：$[1, 1]$、$[1, 2]$ 和 $[2, 1]$。第一种有两名玩家戴颜色 1 的帽子，因此无效，但后两种有效。因此答案为 2。

样例 #2 是题目描述中图示的情况，颜色 1 为黄色，颜色 2 为蓝色。此时被选为 "geese" 的玩家总数必须在 2 到 3 之间，因为选择 4 名 "geese" 会导致至少一种颜色超出范围。对于选择 2 名 "geese" 的情况，唯一的要求是不能选择两名都戴颜色 1 帽子的玩家；所有 5 种此类选择均有效。如果选择 3 名 "geese"，选项为 $[1, 2, 1]$、$[2, 1, 2]$、$[1, 2, 2]$、$[2, 2, 1]$ 或 $[2, 1, 2]$。除第一种外，其余均有效，因此又增加了 4 种有效选项，总计 9 种。

在样例 #3 中，注意可能存在无人佩戴的帽子颜色。由于只有一名玩家戴颜色 3 的帽子，而 1 不在范围内，因此唯一有效的方式是选择 0 名戴该颜色帽子的玩家。

限制

• $1 \leq \mathbf{T} \leq 100$。
• $2 \leq \mathbf{C} \leq \mathbf{N}$。
• 对于所有 $i$，$0 \leq \mathbf{A}_i \leq \mathbf{B}_i \leq \mathbf{N}$。
• 对于所有 $j$，$1 \leq \mathbf{P}_j \leq \mathbf{C}$。

测试集 1（12 分，可见判题结果）

• $3 \leq \mathbf{N} \leq 1000$。

测试集 2（13 分，隐藏判题结果）

• $3 \leq \mathbf{N} \leq 10^5$。

翻译由 DeepSeek V3 完成