Contexto

Tras finalizar varios proyectos interesantes, el lugar del evento recibió una pausa para el café. Mientras conversaban, los presentes hablaron sobre las dificultades de la investigación científica y el proceso de envío de artículos: el autor T se lamentó de que, tras cada envío, debe retirar y volver a enviar su artículo constantemente para pulirlo; por su parte, el revisor S comentó que, al revisar, siempre es estricto y trata de filtrar la mayor cantidad de manuscritos posible.

A raíz de esta conversación, T y S se preguntaron: ¿qué pasaría si el camino hacia la publicación de un artículo se enfrentara a un revisor extremadamente exigente? Así, propusieron un modelo de juego. En este modelo, ambas partes actúan como autor y revisor, respectivamente, en una larga cola de revisión. La cola contiene una gran cantidad de manuscritos de otras personas, entre los cuales solo uno es el enviado por el autor. El autor desea que su artículo circule repetidamente en la cola para pulirlo y maximizar su valor académico al momento de la publicación; mientras que el revisor busca filtrar rigurosamente los artículos, buscando la oportunidad de rechazar directamente este artículo para que el autor no obtenga nada.

La cola de revisión consta de $n$ artículos, donde el $m$-ésimo artículo es el enviado por el autor. Inicialmente, el valor académico de este artículo es 1.

El juego comienza con el autor, y luego ambos turnos se alternan. En cada turno, el jugador debe realizar las siguientes operaciones en orden:

1. Extraer $k$ artículos del frente de la cola de revisión. Si quedan menos de $k$ artículos en la cola, se extraen todos ellos.
2. De los artículos extraídos, elegir 0 o 1 artículo para publicar o rechazar permanentemente, es decir, eliminarlo por completo.
3. Reinsertar todos los artículos no eliminados al final de la cola de revisión en cualquier orden. Dado que la cola de revisión es pública, ambas partes conocen con precisión la nueva posición de cada artículo después de la reinserción.

La puntuación final del autor está determinada por el resultado de su artículo:

• En cada turno, si el artículo no ha sido eliminado y es reinsertado al final de la cola, su valor académico aumenta en 1.
• Si el autor elimina voluntariamente su artículo en alguna operación, el artículo se publica con éxito, el juego termina inmediatamente y el autor obtiene el valor académico actual.
• Si el revisor elimina el artículo del autor en alguna operación, el artículo es rechazado permanentemente, el juego termina inmediatamente y el autor obtiene 0 puntos.

El objetivo del autor es maximizar su puntuación, mientras que el objetivo del revisor es minimizar la puntuación del autor.

Cada caso de prueba contiene múltiples conjuntos de datos. La primera línea de la entrada contiene un entero positivo $T$ ($1 \le T \le 50$), que indica el número de casos de prueba. Para cada conjunto de datos:

• La primera línea contiene tres enteros positivos $n, k, m$ ($1 \le n, k \le 10^9$, $1 \le m \le n$), que representan la longitud de la cola de revisión, el número de artículos extraídos en cada turno y la posición inicial del artículo del autor, respectivamente.

Para cada conjunto de datos, imprima una línea con un entero que represente la puntuación final del autor. En particular, si el juego no termina, imprima $-1$.

Ejemplos

Entrada 1

6
3 2 1
5 3 4
10 3 1
7 3 7
817247666 7237 327476688
610723117 332458760 292738094

Salida 1

2
0
2
4
3470
278264358