1038 Bugs Integrated, Inc.

原文

時間制限:15000ミリ秒
メモリ制限:30000KB
ケース別時間制限: 5000ミリ秒

バグインテグレート株式会社

問題

バグインテグレート株式会社は、高性能メモリチップの大手メーカーである。彼らは新しいテラバイトQ-RAMチップの製造を開始しようとしている。各チップは6つの正方形ユニットを2*3の長方形になるように並べた形からなる。Q-RAMチップを作るために、まず正方形ユニットがN*M個配置された1枚の長方形のシリコンプレートが作られる。そして全ての正方形ユニットが慎重にテストされ、質の悪いものは黒くマークされる。

最終的に、シリコンプレートはいくつかのメモリチップに切りわけられる。各チップは2*3または3*2の正方形ユニットからなる。もちろん、どのチップも質の悪い正方形ユニットを含んではならない。もしかしたら、全ての質の良い正方形ユニットをいずれかのメモリチップの部分として使うことはできないかもしれない。バグインテグレーテッド株式会社は、使用されない質の良い正方形ユニットの数を最小限に抑えたい。そこで彼らは、どのようにシリコンプレートを切りわければメモリチップを最も多く切りとることができるか知りたいと考えた。

いくつかのシリコンプレートについて、その大きさと、質の悪い正方形ユニットのリストが与えられる。あなたの仕事は、各シリコンプレートについて、プレートから切りとることのできるチップの最大数を計算するプログラムを書くことである。

入力

入力の最初の行はシリコンプレートの枚数をあらわす1つの整数D(1 <= d <= 5)からなる。続く行はD個のシリコンプレートそれぞれに対応するブロックを記述する。各ブロックの最初の行は3つの整数N(1 <= N <= 150)、M(1 <= M <= 10)、K(0 <= K <= MN)が空白を区切りとして書かれている。Nはシリコンプレートの長さであり、Mはその高さである。Kはシリコンプレート上の質の悪い正方形ユニットの数である。続くK行はそれぞれ質の悪い正方形ユニットについて記述している。各行は2つの整数xとy(1 <= x <= N, 1 <= y <= M) からなり、それぞれの悪い正方形ユニットの座標を意味する。(左上の座標は[1,1]であり、右下は[N,M]である。)

出力

入力の各シリコンプレートについてそれぞれ、そのプレートから切りとることのできるメモリチップの最大数を含む1行を出力せよ。

入力例

2
6 6 5
1 4
4 6
2 2
3 6
6 4
6 5 4
3 3
6 1
6 2
6 4

出力例

3
4

出典

CEOI 2002