Mô tả đề bài

Cho một sàn nhà hình chữ nhật kích thước ~n \times m~. Hãy tính số lượng gạch lục giác cần dùng để lát sao cho cạnh của viên gạch phải nằm song song với cạnh của sàn nhà như một trong 2 hình dưới.

Input format

• Dòng đầu là một số nguyên không âm ~t~ (~1 \le t \le 1000~) thể hiện số testcase.
• Ứng với mỗi test case là bộ 3 số nguyên không âm ~n~, ~m~ và ~x~ với ~1 \le x \le n, m \le 10^9~ với ~n~, ~m~ là kích thước sàn nhà và ~x~ là độ dài một cạnh của viên gạch

Output format

Gồm ~t~ dòng, mỗi dòng là số lượng viên gạch ít nhất được dùng.

Sample Input

2
3 3 2
10 8 2

Sample Output

3
10

Giải thích ví dụ

Testcase 1

Testcase 2