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.
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.
Dla każdego zestawu danych wejściowych program ma wypisać jeden wiersz zawierający minimalną liczbę przecięć koniecznych do pocięcia arkusza na plakaty.
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
3
2
20
7
5
6
3
10
12