在游戏“Duck, Duck, Goose”中，除了一个人之外，所有玩家都坐在地板上围成一个圆圈。剩下的那个人绕着圆圈走，称呼每个玩家为“duck”（鸭子），直到他们选中一名坐着的玩家，并在摸其头时将其称为“goose”（鹅）。此时，那只“鹅”会追逐选择者，而我们对游戏的兴趣也就随之消退了。

在新的游戏“Duck, Duck, Geese”中，走动的那名玩家改为选择一个包含至少两名（但不能是全部）坐着玩家的连续子集作为“鹅”！此外，每名坐着的玩家都戴着一顶帽子。每顶帽子有 $C$ 种可能的颜色，编号为 $1$ 到 $C$。

对于每种颜色 $i$，所选出的戴着颜色 $i$ 帽子的“鹅”的数量必须为 $0$，或者在 $A_i$ 到 $B_i$ 之间（包含边界）。

你能帮忙计算满足这些要求的选择方案数吗？如果两种选择中包含的玩家集合不同，则视为不同的选择。

输入格式

第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $C$：分别表示坐着的玩家人数和帽子的颜色数量。接下来有 $C$ 行。第 $i$ 行包含两个整数 $A_i$ 和 $B_i$，含义如上所述。测试用例的最后一行包含 $N$ 个整数 $P_1, P_2, \dots, P_N$，表示按顺时针顺序（从任意一人开始）坐着的第 $j$ 位玩家戴着颜色为 $P_j$ 的帽子。

输出格式

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

数据范围

$1 \le T \le 100$ $2 \le C \le N$ $0 \le A_i \le B_i \le N$，对于所有 $i$ $1 \le P_j \le C$，对于所有 $j$

子任务 1

$3 \le N \le 1000$

子任务 2

$3 \le N \le 10^5$

样例

样例输入 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

样例输出 1

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

说明

在样例 1 中，被选为“鹅”的玩家总数必须为 2。选择 2 名玩家的方法只有三种。可能的颜色配置为：$[1, 1]$，$[1, 2]$ 和 $[2, 1]$。第一种配置中有两名玩家戴着颜色 1 的帽子，因此不符合要求，但另外两种是有效的。因此答案为 2。

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

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

Figure 1. 样例 2 是题目描述中展示的情形，颜色 1 为黄色，颜色 2 为蓝色。