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\)