휴식

과제를 해결하다 지친 민준이는, 승민이와 다음과 같은 게임을 $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$번째 게임 종료 후 승민이가 얻는 점수를 출력한다.