Description

东海岸有$N$ 个城市，西海岸有$M$ 个城市 $（N ≤1000，M ≤1000）$，将建成$K$ 条高速公路。每个海岸的城市从北 到南编号为$1, 2, ……$每条高速公路都是直线，连接东海岸的城市和西 海岸的城市。建设资金由高速公路之间的交叉数决定。两个高速公路最 多在一个地方交叉。请计算高速公路之间的交叉数量。

Format

Input

输入文件以$T$ 为开头，表示测试用例的数量。每个测试用 例都以$3$个数字$N 、M 、K$为开头。下面$K$ 行中的每一行都包含两个数 字，表示由高速公路连接的城市号。第$1$个是东海岸的城市号，第$2$个是 西海岸的城市号。

Output

对每个测试用例，都单行输出“Test case $x$ :$s$ ”，$x$ 表示输入样例编号，$s$ 表示交叉数。

Samples

1
3 4 4
1 4
2 3
3 2
3 1

Test case 1:5

来源

POJ3067