Opis

Państwo MWPZtowo rozwija się ostatnio w nieprawdopodobnym tempie. Powstają kolejne firmy, sklepy, instytucje. Jak to zwykle w takich sytuacjach, rozwija się też bardzo silnie branża reklamowa. Powstają różnego rodzaju banery, plakaty, wywieszki, tablice, a także neony. Tych ostatnich powstaje tak wiele, że już nikt nigdy nie będzie mógł powiedzieć jadąc za granicę, że „tutaj jest więcej neonów na jednej ulicy, niż u nas w całej stolicy”. Jak to zwykle też bywa, rozwój jednej branży powoduje rozwój kolejnych, w tym przypadku także informatycznej. Neony trzeba odpowiednio oprogramować, tak aby wyświetlały dokładnie to, czego chcą ich właściciele. To właśnie jest Twoje nowe zadanie.

Każdy neon to pewien prostokątny układ lampek, z których odpowiednie kształty, napisy, wzorki (cokolwiek sobie klient zażyczy) są wyświetlane przy pomocy zapalania i gaszenia odpowiednich lampek. Neon oczywiście co jakiś czas zmienia to co wyświetla. Robi to gasząc lub zapalając odpowiednie lampki. Dokonuje się to poprzez zamykanie i otwieranie dla każdej z lampek obwodu elektrycznego, który albo doprowadzi prąd do lampki (wtedy lampka się pali) albo przerywa go i wtedy nie ma w lampce prądu (wtedy lampka jest zgaszona). Koszt pojedynczego „pstryczka” do zamykania i otwierania obwodu jest bardzo duży. Na szczęście nie trzeba robić osobnego włącznika/wyłącznika dla każdej z lampek. Można je połączyć w pewne grupy, takie, które zawsze są razem zapalone lub zgaszone. Dzięki temu dla takiej jednej grupy możemy zrobić tylko jeden pstryczek który będzie odpowiedzialny za zapalanie i gaszenie całej grupy lampek. Każdą lampkę można podłączyć tylko pod jeden pstryczek, czyli dwa różne pstryczki nie mogą odpowiadać za jedną lampkę. Cały prostokąt pokryty jest lampkami - nawet jeśli lampka nigdy nie zostanie zapalona, należy ją podłączyć pod jakiś pstryczek. Ponieważ koszt neonu to w zasadzie koszt tych pstryczków, Twój program powinien na początek obliczać cenę neonu poprzez podanie, ile co najmniej pstryczków będzie potrzebnych do zbudowania projektowanego neonu, tak by było możliwe wyświetlenie wszystkich obrazków, których klient sobie życzy.

Specyfikacja wejścia

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę różnych neonów, które trzeba będzie oprogramować. Pierwsza linia każdego zestawu danych zawiera trzy liczby całkowite M, N, K (1 ≤ M,N ≤ 1000; 0 ≤ K ≤ 1000), gdzie M i N to szerokość i wysokość neonu, zaś K oznacza liczbę przedstawianych na tym neonie obrazków. Następnie znajduje się opis K obrazków. W pierwszej linii opisu znajduje się liczba całkowita L (1 ≤ L ≤ N×M) określająca liczbę jasnych punktów na neonie. W następnych L liniach znajdują się współrzędne tych punktów, liczby całkowite x,y (1 ≤ x  ≤ M, 1 ≤ y ≤ N), gdzie x oznacza numer kolumny (numerując od lewej), a y oznacza numer wiersza (numerując od góry), w którym znajduje się lampka. Można założyć że suma wszystkich zapalonych punktów na wszystkich obrazkach nie będzie większa niż 1000000 (tj. milion).

Specyfikacja wyjścia

Dla każdego zestawu danych wypisz w osobnej linii jedną liczbę całkowitą oznaczającą minimalną liczbę pstryczków potrzebnych do zbudowania neonu.

Przykład

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

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

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

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

3
13

Ilustracja przykładu drugiego:

Wejście:

Można je podzielić na takich 13 grup lampek podłączonych do jednego pstryczka: