비 오는 날

비 오는 날 $N$명의 학생이 창의인재관에서 융합인재관으로 건너가려고 한다. 창의인재관에는 $M$개의 우산이 있고, 융합인재관에는 우산이 없다. 한 우산은 한 번에 최대 $K$명까지 쓸 수 있다. 학생들은 다음 시행을 반복해 건너갈 수 있다.

• 한 건물에 있는 학생 중 몇 명이 우산을 쓰고 다른 건물로 넘어간다. 이때, 모두가 같은 우산을 쓸 필요는 없다.
• 아무도 쓰고 있지 않은 우산은 학생들이 제한 없이 들고 갈 수 있다. 예를 들어, 1명의 학생이 1개의 우산을 쓰고 3개의 우산을 들고 가는 것이 가능하다.

모든 학생이 비를 맞지 않고 융합인재관으로 건너갈 수 있는지 판별하여라. 건너갈 수 있다면, 모든 학생이 건너가기 위한 시행의 최소 횟수를 구하여라. 단, 모든 우산을 융합인재관으로 가지고 올 필요는 없다.

엄밀히 말해, 4개의 정수로 이루어진 순서쌍 $(a,b,c,d)$가 주어진다. 이는 현재 창의인재관에 있는 학생이 $a$명, 창의인재관에 있는 우산이 $b$개, 융합인재관에 있는 학생이 $c$명, 융합인재관에 있는 우산이 $d$개라는 뜻이다. 초기에 $a=N$, $b=M$, $c=d=0$이며, 최소 횟수의 시행을 통해 $c=N$으로 만들어야 한다. 시행은 다음 행동 중 하나를 하는 것으로 정의된다.

• 두 양의 정수 $x$, $y$를 선택하여 순서쌍 $(a,b,c,d)$를 $(a-x,b-y,c+x,d+y)$로 바꾼다. 이는 창의인재관에서 $x$명의 학생이 $y$개의 우산을 이용하여 융합인재관으로 이동한다는 뜻이다. 이때, $0 < x \le a$와 $0 < y \le b$와 $x \le Ky$이어야 한다.
• 두 양의 정수 $z$, $w$를 선택하여 순서쌍 $(a,b,c,d)$를 $(a+z,b+w,c-z,d-w)$로 바꾼다. 이는 융합인재관에서 $z$명의 학생이 $w$개의 우산을 이용하여 창의인재관으로 이동한다는 뜻이다. 이때, $0 < z \le c$와 $0 < w \le d$와 $z \le Kw$이어야 한다.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.

다음 $T$개의 줄 중 $i$번째 줄에는 $i$번째 테스트 케이스를 나타내는 세 정수 $N$, $M$, $K$가 띄어쓰기를 사이에 두고 주어진다.

$T$개의 줄에 걸쳐, $i$번째 줄에는 $i$번째 테스트 케이스의 답에 해당하는 정수 1개를 출력한다. 모든 학생이 융합인재관으로 건너갈 수 있다면 모든 학생이 건너가기 위한 시행의 최소 횟수를 출력하고, 그렇지 않다면 -1을 출력한다.

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