26610번 - 돌게임과 쿼리

문제

경곽이는 돌게임을 만들고, 영재에게 이 게임과 관련된 문제를 내었다. 돌게임은 구체적으로 $N$개의 돌을 가져가는 게임인데, 각 턴에는 반드시 1ドル$개 이상의 돌을 가져가야 하며, $I$번째 턴에는 $(X+I)$의 배수만큼의 돌을 가져갈 수 있다. 하지만 한 턴에 돌을 너무 많이 가져가는 것을 싫어하는 경곽이는 이 게임에 새로운 규칙을 추가했다. 구체적으로, $I$번째 턴에는 최대 $(X+I) \times T$개의 돌만 가져갈 수 있다. 만약 현재 턴에서 더 이상 돌을 가져갈 수 없으면 게임이 종료된다. 영재에게 낸 문제는 다음과 같다. 게임이 종료되었을 때 남은 돌의 개수를 최소화시켜야 한다. 만약 남은 돌의 개수가 같다면, 게임이 최대한 빨리 종료되도록 해야 한다. 최선의 방법으로 게임을 진행할 때 필요한 게임의 턴 수를 구하여라. 하지만 똑똑한 영재가 이를 너무 쉽게 구하자, 화가난 경곽이는 여러 질의를 주고 답을 구하라고 하였다. 영재를 도와 문제를 해결해보자.

입력

첫 번째 줄에 쿼리의 개수 $Q$가 주어진다.

다음 줄부터 쿼리에 대한 정보 $X$ $T$ $N$이 순서대로 주어진다.

출력

$i$번째 줄에 $i$번 쿼리에서 주어진 조건의 돌게임에서 영재가 구해야 하는 답을 출력하라. 즉, 필요한 최소의 턴 수를 출력하라.

제한

• 1ドル \leq Q \leq 3 \times 10^{5}$
• 1ドル \leq X < N \leq 5 \times 10^{8}$
• 2ドル \leq T \leq 10^{8}$

힌트