Contexte du problème

Plusieurs projets intéressants touchent à leur fin, et la conférence accueille une pause-café. Au cours des discussions, les participants évoquent les difficultés de la recherche scientifique et de la soumission d'articles : T exprime son regret de devoir constamment retirer et resoumettre ses articles après chaque soumission, les polissant sans cesse ; tandis que S, en tant que relecteur, affirme qu'il est toujours très strict lors de ses évaluations, essayant d'éliminer autant de manuscrits que possible.

Suite à cet échange, T et S ont une idée originale : que deviendrait le processus de publication d'un article s'il était confronté à un relecteur extrêmement exigeant ? Ils ont donc élaboré un modèle de jeu. Dans ce modèle, les deux parties jouent respectivement le rôle de l'auteur et du relecteur, s'affrontant autour d'une longue file d'attente de révision. La file contient un grand nombre de manuscrits d'autres personnes, dont un seul a été soumis par l'auteur. L'auteur souhaite que son article circule dans la file d'attente pour être poli à plusieurs reprises, afin d'augmenter autant que possible sa valeur académique finale lors de sa publication ; tandis que le relecteur effectue un filtrage rigoureux, cherchant des occasions de rejeter directement cet article pour que l'auteur ne reçoive rien.

Description

La file d'attente de révision se compose de $n$ articles, dont le $m$-ième est l'article soumis par l'auteur. Initialement, la valeur académique de cet article est de 1.

Le jeu commence par l'auteur, puis les deux parties jouent à tour de rôle. À chaque tour, le joueur dont c'est le tour doit effectuer les opérations suivantes dans l'ordre :

1. Extraire successivement $k$ articles du début de la file d'attente. Si le nombre d'articles restants dans la file est inférieur à $k$, les extraire tous ;
2. Parmi les articles extraits, choisir d'en publier ou d'en rejeter définitivement 0 ou 1, c'est-à-dire de le retirer complètement de la file ;
3. Réinsérer tous les articles non retirés à la fin de la file d'attente dans l'ordre de son choix. Comme la file d'attente est entièrement publique, les deux parties connaissent précisément la nouvelle position de chaque article après la réinsertion.

Le score final de l'auteur est déterminé par le résultat de son article :

• À chaque tour, si l'article n'est pas retiré et est réinséré à la fin de la file, sa valeur académique augmente de 1 ;
• Si l'auteur retire volontairement son article lors d'une opération, l'article est publié avec succès, le jeu se termine immédiatement et l'auteur obtient la valeur académique actuelle ;
• Si le réviseur retire l'article de l'auteur lors d'une opération, l'article est définitivement rejeté, le jeu se termine immédiatement et l'auteur obtient un score de 0.

L'objectif de l'auteur est naturellement de maximiser son score, tandis que l'objectif du réviseur est de minimiser le score de l'auteur.

Tu dois calculer le score final de l'auteur lorsque l'auteur et le réviseur adoptent tous deux une stratégie optimale.

Chaque cas de test contient plusieurs jeux de données. La première ligne contient un entier positif $T$ ($1 \le T \le 50$), représentant le nombre de jeux de données. Pour chaque jeu de données :

• La première ligne contient trois entiers positifs $n, k, m$ ($1 \le n, k \le 10^9$, $1 \le m \le n$), représentant respectivement la longueur de la file d'attente, le nombre d'articles extraits à chaque tour, et la position initiale de l'article soumis par l'auteur.

Pour chaque jeu de données, afficher un entier sur une ligne, représentant le score final de l'auteur. En particulier, si le jeu ne se termine jamais, afficher $-1$.

Exemples

Entrée 1

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

Sortie 1

2
0
2
4
3470
278264358