오리, 오리, 거위들

"오리, 오리, 거위" 게임에서는 한 명을 제외한 모든 참가자가 바닥에 앉아 원을 이룬다. 남은 참가자는 원 주위를 걸으며 앉아 있는 참가자들을 차례로 "duck"라고 부르다가, 그중 한 명을 선택해 머리를 만지면서 대신 "goose"라고 부른다. 그 순간 거위가 선택한 참가자를 쫓기 시작하고, 이 게임에 대한 우리의 관심은 사라진다.

새로운 게임 "오리, 오리, 거위들"에서는 걸어 다니는 참가자가 대신 앉아 있는 참가자 중 연속한 적어도 두 명(단, 전부는 아님)을 골라 "geese"로 정한다! 또한 앉아 있는 각 참가자는 모자를 쓰고 있다. 각 모자는 가능한 $\mathbf{C}$가지 색 중 하나이며, 색에는 $1$부터 $\mathbf{C}$까지 번호가 매겨져 있다.

각 색 $i$에 대해, 선택된 거위 중 색 $i$의 모자를 쓴 거위의 수는 $0$이거나, $\mathbf{A_i}$ 이상 $\mathbf{B_i}$ 이하이어야 한다.

이 조건을 만족하는 선택의 수를 구해 보자. 어떤 참가자가 한 선택에는 포함되지만 다른 선택에는 포함되지 않는다면 두 선택은 서로 다른 것으로 간주한다.

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $2 \le \mathbf{C} \le \mathbf{N}$. 모든 $i$에 대해 $0 \le \mathbf{A_i} \le \mathbf{B_i} \le \mathbf{N}$. 모든 $j$에 대해 $1 \le \mathbf{P_j} \le \mathbf{C}$.

테스트 세트 1 (Visible Verdict)

$3 \le \mathbf{N} \le 1000$.

테스트 세트 2 (Hidden Verdict)

$3 \le \mathbf{N} \le 10^5$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 앉아 있는 참가자의 수와 모자 색의 수를 각각 나타내는 두 정수 $\mathbf{N}$와 $\mathbf{C}$가 포함된 줄로 시작한다. 그다음 $\mathbf{C}$개의 줄이 주어진다. 이 줄들 중 $i$번째 줄에는 위에서 설명한 두 정수 $\mathbf{A_i}$와 $\mathbf{B_i}$가 주어진다. 테스트 케이스의 마지막 줄에는 시계 방향으로(임의의 한 명부터 시작하여) $j$번째로 앉아 있는 참가자가 색 $\mathbf{P_j}$의 모자를 쓰고 있음을 나타내는 $\mathbf{N}$개의 정수 $\mathbf{P_1}, \mathbf{P_2}, \dots, \mathbf{P_N}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 연속해서 앉아 있는 참가자를 적어도 $2$명, 최대 $\mathbf{N}-1$명 선택하여 모든 색 조건을 만족하는 집합의 수이다.

예제 케이스 #1에서는 거위로 선택한 참가자의 총수가 $2$이어야 한다. $2$명의 참가자를 선택하는 방법은 단 세 가지뿐이다. 가능한 색 구성은 $[1, 1]$, $[1, 2]$, $[2, 1]$이다. 첫 번째 구성에는 색 $1$의 모자를 쓴 참가자가 두 명 있으므로 유효하지 않지만, 나머지 두 구성은 유효하다. 따라서 답은 $2$이다.

예제 케이스 #2은 문제 설명에 그림으로 제시된 경우로, 색 $1$은 노란색이고 색 $2$는 파란색이다. 이 경우 거위로 선택한 참가자의 총수는 $2$ 이상 $3$ 이하여야 한다. $4$마리의 거위를 선택하면 적어도 한 색이 허용 범위를 벗어나기 때문이다. 거위가 $2$마리인 경우에는 색 $1$의 모자를 쓴 거위 $2$마리를 모두 선택하지 않아야 한다는 조건만 있으며, 그러한 선택 $5$개는 모두 유효하다. 거위 $3$마리를 선택하는 경우 가능한 선택은 $[1, 2, 1]$, $[2, 1, 2]$, $[1, 2, 2]$, $[2, 2, 1]$, $[2, 1, 2]$이다. 첫 번째를 제외하면 모두 유효하므로 유효한 선택이 $4$개 더 추가되어, 총 $9$개가 된다.

예제 케이스 #3에서는 아무도 쓰고 있지 않은 모자 색이 있을 수 있다는 점에 유의하라. 이 경우 모자 색 $3$을 쓴 참가자가 $1$명뿐이고 $1$은 범위에 포함되지 않으므로, 그 모자 색을 쓴 참가자 $0$명을 선택하는 것만이 유효하다.