3067 Japan

原文

時間制限:1000ミリ秒
メモリ制限:65536KB

問題

日本はACM ICPC World Finals を歓迎するつもりである。そのため、会場として多くの道を建設しなければならない。日本は、東海岸のN 都市と西海岸のM 都市(N,M <= 1000) からなる島国である(という設定になっている)。各都市は、北から南まで、1, 2, . . . と番号付けられる。K (K <= NM) 本の高速道路が建設される。高速道路は直線で、西海岸の都市と東海岸の都市を結ぶ。建設のための資金は、ACM によって援助される。金額の大部分は、高速道路同士が交差する回数によって決定される。3 本以上の高速道路が、1 箇所で交わることはない。このとき、高速道路間の交差の回数を求めるプログラムを作成せよ。

入力

入力はいくつかのテストケースを含む。1 行目には、テストケースの個数を示す整数が書かれている。それぞれのテストケースにおいて、最初の行には、N,M,K が空白区切りで書かれている。その後のK行には、高速道路の情報が書かれている。各行には、2つの整数を、空白区切りで書かれている。最初の整数は東海岸の都市の番号である。次の整数は西海岸の都市の番号である。

出力

各テストケースに対し、次のように1 行を出力せよ。

Test case (テストケース番号): (高速道路の交差の回数)

入力の例

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

出力の例

Test case 1: 5

出典

Southeastern Europe 2006