Bạn có một mặt phẳng hai chiều và có một số đường thẳng trên mặt phẳng này: Cụ thể có \(H\) đường kẻ ngang và \(V\) đường kẻ dọc. Những đường thẳng này chính là biên giới giữa các miền trong mặt phẳng. Bạn cần chia mặt phẳng đã cho thành ít nhất \(N\) miền, biết rằng bạn được quyền kẻ thêm những đường thẳng ngang hoặc dọc.

Yêu cầu: Hỏi bạn cần thêm ít nhất bao nhiêu đường thẳng (ngang hoặc dọc) để đáp ứng yêu cầu bài toán.

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số testcase

• \(t\) dòng tiếp theo, mỗi dòng gồm \(3\) số nguyên \(H,V,N(1\le H,V\le 10^6,1\le N\le 10^{14})\)

Output

• Ứng với mỗi testcase in ra đáp án cần tìm

Example

1
4 0 20

3

    |  |  |
1| 2| 3| 4
----+--+--+----
5| 6| 7| 8
----+--+--+----
9|10|11|12
----+--+--+----
13|14|15|16
----+--+--+----
17|18|19|20
    |  |  |