Khôi rất thích chơi Liên Minh Huyền Thoại, đặc biệt là vị tướng Yasuo. Tuy nhiên anh ấy chơi Yasuo rất tệ nên anh ấy đang tập luyện để chơi vị tướng này một cách thành thạo.

Biết rằng từ tọa độ \((x,y)\) Yasuo có thể lướt thẳng đến một trong các vị trí $(x-1,y), (x+1,y), (x,y-1), (x,y+1) $

hoặc lướt chéo đến một trong các vị trí \((x-1,y-1), (x-1,y+1), (x+1,y-1), (x+1,y+1)\)

Khôi sẽ tập luyện lướt Yasuo trong \(Q\) trận, trong trận thứ \(i\) mục tiêu của anh ấy là lướt tới điểm \((n,m)\) từ tọa độ \((0,0)\) trong chính xác \(k\) lần lướt. Tuy nhiên vì để được Thông Thạo 7 Yasuo, Khôi sẽ lướt đến điểm \((n,m)\) với số lần lướt chéo là nhiều nhất.

Câu hỏi của bạn là, trong trận thứ \(i\), bạn hãy xác định số lần lướt chéo nhiều nhất của Khôi hoặc nói rằng Khôi không thể lướt từ điểm \((0,0)\) tới điểm \((n,m)\) trong chính xác \(k\) lần lướt.

Input

• Dòng đầu tiên: Số nguyên dương \(Q\) \((Q \leq 10^4)\) - số câu hỏi
• \(Q\) dòng tiếp theo chứa số nguyên dương \(n\), \(m\), \(k\) \((n,m,k \leq 10^{18})\)

Output

• Gồm \(Q\) dòng, tại dòng thứ \(i\), in ra \(“-1”\) nếu Khôi không thể lướt từ điểm \((0,0)\) đến điểm \((n,m)\) trong chính xác \(k\) lần lướt, ngược lại in ra số lần lướt chéo nhiều nhất của Khôi

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n,m \leq 10\)
• Subtask \(1\) (\(50\%\) số điểm): \(n,m \leq 10^{18}\)

Example

3
2 2 3
4 3 7
10 1 9 

1
6
-1