Đề 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

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 đầu tiên chứa số nguyên t (1 ≤ t ≤ 10⁴) — số lượng test case.

Mỗi test case gồm một dòng chứa ba số nguyên dương n, m, k (1 ≤ n, m, k ≤ 10⁹, k ≤ n·m).

Output

Với mỗi test case, in ra một số duy nhất — 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