Ghế dài tối ưu

Đề bài
Trong hội trường thi được bố trí theo hình chữ nhật.

Hội trường có n hàng, mỗi hàng có m chỗ để bàn.

Có tổng cộng k thí sinh, mỗi thí sinh ngồi tại một bàn riêng.

Ban tổ chức cần chọn vị trí các bàn sao cho sắp xếp hợp lý.

Ghế dài :

Nếu nhiều bàn được đặt liền nhau trong cùng một hàng, chúng tạo thành một ghế dài.
Chiều dài của ghế dài là số bàn trong nhóm này.

Ví dụ: sắp xếp 7 thí sinh trên hội trường 3×4 (n=3, m=4) có thể như sau:

• Hàng 1: một ghế dài dài 3
• Hàng 2: một ghế dài dài 2
• Hàng 3: hai ghế dài dài 1

Tổng thể, ghế dài lớn nhất có độ dài 3.

Tuy nhiên, nếu sắp xếp lại, ta có thể thu được cách tối ưu hơn:
Trong cách này, độ dài ghế dài lớn nhất chỉ là 2.

Mục tiêu:

Sắp xếp các bàn sao cho chiều dài của ghế dài dài nhất là nhỏ nhất có thể.

Input

• Dòng 1: Gồm một số nguyên t là số lượng bộ test
• t dòng tiếp theo gồm ba số nguyên n, m, k — số hàng, số cột và số thí sinh.

Output

• In ra chiều dài nhỏ nhất có thể của ghế dài dài nhất.

Sample Input

5
3 4 7
5 5 5
1 13 2
2 4 7
1 5 4

Sample Output

2
1
1
4
2