CF2215F Research

Research: Draw cards from 1 of the facedown Level Decks equal to your Research Amount. You may choose 1 to Build or File. Alice and Bob will play a game with a deck of cards. This deck consists of $ n-1 $ white cards and one green card. Initially, the green card is located at the $ s $ -th place from the top of the deck, with the number $ 1 $ written on it. Both Alice and Bob know the place of the green card. Alice goes first. In each turn, they should proceed as follows: - Take $ k $ cards from the top of the deck. (If the deck has fewer than $ k $ cards, take all of them.) After that, discard $ 0 $ or $ 1 $ card among those $ k $ cards, and put the remaining cards at the bottom of the deck in any order they like. - If the green card is discarded by Bob, the game ends immediately with a score of $ 0 $ . - If the green card is discarded by Alice, the game ends immediately with a score equal to the number written on the green card. - If Alice takes the green card and returns it to the deck, she should tell Bob the new location of the green card and increase the number on the green card by $ 1 $ . Alice needs to maximize the score, while Bob needs to minimize it. You have to find the final score of the game if both of them play optimally.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 50 $ ). The description of the test cases follows. The only line of each test case contains three integers $ n $ , $ k $ , and $ s $ ( $ 1\le n,k\le 10^9 $ , $ 1\le s\le n $ ).

For each test case, if the game will never end, output a line with the word Infinity; otherwise, output a single integer — the score of the game.

In the first test case, an optimal process of the game is as follows. Alice should take $ 2 $ cards from the top, discard nothing, and return the green card to the bottom of the deck. Then Bob should take $ 2 $ white cards from the top and discard one. On the third turn, Alice should discard the green card with the number $ 2 $ written on it. In the second test case, Bob will take the green card first and discard it. Therefore, the score should be $ 0 $ .