Rainy Day

On a rainy day, $N$ students want to cross from the Creative Talent Hall to the Convergence Talent Hall. The Creative Talent Hall has $M$ umbrellas, and the Convergence Talent Hall has none. One umbrella can be shared by up to $K$ students at a time. The students repeat the following operations to cross.

• Some of the students in one building cross to the other building using umbrellas. They do not all need to use the same umbrella.
• Any umbrella that nobody is using can be taken along without limit. For example, one student can use one umbrella and carry three more.

Determine whether all students can cross without getting wet. If they can, find the minimum number of operations needed for all students to cross. Not every umbrella has to be brought to the Convergence Talent Hall.

Strictly speaking, the state is an ordered quadruple $(a,b,c,d)$, where $a$ is the number of students in the Creative Talent Hall, $b$ is the number of umbrellas in the Creative Talent Hall, $c$ is the number of students in the Convergence Talent Hall, and $d$ is the number of umbrellas in the Convergence Talent Hall. Initially $a=N$, $b=M$, $c=d=0$, and the goal is $c=N$ in the fewest operations. An operation is one of the following.

• Choose two positive integers $x$ and $y$ and change $(a,b,c,d)$ to $(a-x,b-y,c+x,d+y)$. This means $x$ students move from the Creative Talent Hall to the Convergence Talent Hall using $y$ umbrellas. Here $0 < x \le a$, $0 < y \le b$, and $x \le Ky$ must hold.
• Choose two positive integers $z$ and $w$ and change $(a,b,c,d)$ to $(a+z,b+w,c-z,d-w)$. This means $z$ students move from the Convergence Talent Hall to the Creative Talent Hall using $w$ umbrellas. Here $0 < z \le c$, $0 < w \le d$, and $z \le Kw$ must hold.

The first line contains the number of test cases $T$.

Each of the next $T$ lines contains three integers $N$, $M$, and $K$, separated by spaces.

For each test case, print one integer on its own line. If all students can cross, print the minimum number of operations needed for all students to cross. Otherwise, print -1.

• $1\le T\le 1\, 000$
• $1\le i\le T$
• $1\le N,M,K\le 10$