20562번 - 휴식

문제

과제를 해결하다 지친 민준이는, 승민이와 다음과 같은 게임을 $T$번 진행하려고 한다.

각 게임은 2개의 양의 정수 $N,ドル $M$과 1개의 음이 아닌 정수 $X$로 이루어진다. 각 게임마다 $S$라는 변수가 있으며, 초기에 이 값은 $X$이다.

게임은 $N$턴 동안 이루어지며, 각 턴은 승민이와 민준이가 순서대로 $S$를 변경하는 것으로 이루어진다. 승민이는 한 턴에 한 번, $S$에 0 또는 1을 더할 수 있고, 민준이는 한 턴에 한 번, $S$에 0 또는 1 또는 2를 더할 수 있다.

승민이는 게임 종료 후 $S$의 값을 $M$으로 나눈 나머지만큼의 점수를 얻는다. 승민이는 자신의 점수를 최대화하려고 하고, 민준이는 이를 최소화하려고 한다. 승민이와 민준이가 최선을 다해 게임을 할 때, 승민이가 얻는 점수는 얼마일까?

입력

첫 줄에 게임의 횟수 $T$가 주어진다. (1ドル \leq T \leq 10^6$)

이후 $T$개의 줄에 걸쳐 게임의 정보가 주어진다. $i+1$번째 줄에는 $i$번째 게임의 정보 $N_i,ドル $M_i,ドル $X_i$가 공백으로 구분되어 주어진다. (1ドル \leq N_i, M_i \leq 10^9,ドル 0ドル \leq X_i < M_i$)

출력

$i$번째 줄에 $i$번째 게임 종료 후 승민이가 얻는 점수를 출력한다.

제한

힌트