Wybory (wersja poprawiona)

Mamlaki niebawem wybiorą swego nowego przywódcę. Jest wielu kandydatów do objęcia tej posady, a każdy z nich uważa, że jest najlepszy. Aby o tym wszystkich przekonać kandydaci zamierzają przeprowadzić na szeroką skalę kampanię wyborczą. Jednym z elementów kampanii są rozwieszane plakaty. Główna Komisja Wyborcza chce aby każdy kandydat miał równe szanse, dlatego wydano rozporządzenie zgodnie z którym plakaty wyborcze mają mieć szerokość i wysokość równą 1 metr. Poszczególne sztaby wyborcze złożyły już zamówienie w drukarni na plakaty wyborcze.

Papier na którym zostaną wydrukowane plakaty jest dostarczany do drukarni w arkuszach o wymiarach M x N metrów. Do cięcia arkuszy na plakaty o wymiarach 1 x 1 metr używane są specjalne maszyny o zróżnicowanych parametrach. Część maszyn umożliwia jednoczesne przecięcie kilku arkuszy, natomiast inne pozwalają przeciąć jednocześnie tylko jeden arkusz.

Twoim zadaniem jest napisać program, który dla danej informacji o liczbie arkuszy jakie mogą być przecięte jednocześnie, wyznaczy jaka jest minimalna liczba przecięć koniecznych do pocięcia na plakaty arkusza o danych rozmiarach. Przed każdym przecięciem każdy arkusz może być dowolnie obracany.

Dane wejściowe:

W pierwszym wierszu zapisana jest liczba zestawów danych wejściowych K. W kolejnych wierszach jest zapisanych K zestawów danych wejściowych.

Pojedynczy zestaw danych wejściowych składa się z jednego wiersza zawierającego trzy liczby całkowite M, N i L oddzielone pojedynczym odstępem. Liczby M i N (1 ≤ M, N ≤ 40) określają wymiary arkusza, natomiast L (1 ≤ L ≤ 400) maksymalną liczbę arkuszy jakie mogą być przecięte jednocześnie.

Dane wyjściowe:

Dla każdego zestawu danych wejściowych program ma wypisać jeden wiersz zawierający minimalną liczbę przecięć koniecznych do pocięcia arkusza na plakaty.

Przykładowe dane wejściowe:

9
2 2 1
2 2 2
3 7 1
3 7 4
3 7 9
5 5 200
5 1 10
15 23 100
40 40 400
	

Przykładowe dane wyjściowe:

3
2
20
7
5
6
3
10
12