A group of students wants to visit a tour in some city $X$. In total, the group has $N$ boys and $M$ girls. To do this, they need to stay in a hotel.

Calculate the number of rooms you need to book in the hotel, if each hotel room has $K$ seats, provided that the boys can not live with the girls in the same room.

Input format

• The first line specifies a number $T$ denoting the number of test cases.
• In each line of the test case, there are three numbers, $N,M,K$.

Output format

For each test case, print one number denoting the number of rooms to be booked at the hotel.

Constraints

$1 ⩽ T ⩽ 10$
$0 ⩽ n, m ⩽ 1000$
$n + m > 0$
$1 ⩽ k ⩽ 1000$