Rozważmy następującą planszową grę komputerową. Obszar gry jest prostokątem NxM podzielonym na kwadraty 1x1. Zawodnik w jednej turze może się znajdować w jednym z tych kwadracików, natomiast jakikolwiek jego ruch może się odbywać się tylko pomiędzy turami. W czasie jednego „międzyturza” dozwolone jest tylko przemieszczenie się na sąsiednie pole (w poziomie i w pionie), aczkolwiek gracz może się w ogóle nie ruszać.
Na początku każdej tury na jednym z kwadracików planszy pojawia się diament, a po jej zakończeniu znika. Diament może być zabrany tylko wtedy, gdy zawodnik znajduje się na tym samym kwadraciku.
Twoim zadaniem jest napisanie programu, który na podstawie pozycji kolejnych pojawiających się diamentów określi, ile z nich maksymalnie może być zabranych. Początkowa pozycja gracza jest dowolna.
W pierwszej linii pliku wejściowego znajduje się liczba naturalna d (1 £ d £ 10), określająca liczbę zestawów danych, których opisy umieszczone są kolejno po sobie w następnych liniach pliku. Opis pojedynczego zestawu jest następujący:
W pierwszej linii znajdują się trzy liczby naturalne: liczba wierszy planszy N (1 £ N £ 10), liczba kolumn M (1 £ M £ 10) oraz czas trwania gry w turach T (1 £ T £ 1000). W następnych T liniach znajdują się współrzędne diamentów, które pojawiły się w kolejnych turach podane za pomocą wiersza n (1 £ n £ N) i kolumny m (1 £ m £ M).
Każdemu zestawowi w pliku wejściowym powinna odpowiadać jedna linia pliku wyjściowego. Ta linia powinna zawierać maksymalną możliwą liczbę diamentów do zebrania.
Plik wejściowy
3
3 3 3
1 1
2 2
1 2
3 3 5
1 1
2 3
3 3
3 1
2 2
3 3 3
1 1
1 1
3 1
Plik wyjściowy:
2
3
2