31129번 - Balls 다국어

문제

Alice and Bob are playing a game. They've got $B$ blue and $R$ red balls laid out before them. Alice has the first move, and after that, players alternate moves. Alice picks a random ball and removes it. Bob removes a single red ball.

Alice chooses her balls randomly with equal probability regardless of their color. It does not matter which red ball Bob removes.

The game ends when one of the two outcomes occurs:

• there are no more blue balls --- Alice wins;
• there are strictly more blue balls than there are red balls --- Bob wins.

Alice and Bob would like a balance of outcomes, and are curious as for what number of blue balls is necessary for a game of $C = B + R$ for the probability of Alice winning to be as close to 50ドル\%$ as possible. In other words, they want to minimize the value $\left| h - 0.5 \right|$.

입력

The first line of the input file contains a single integer $G$ --- the number of games Alice and Bob plan to play (1ドル \le G \le 10^5$).

The following lines define the number of balls $C$ in each game(2ドル \le C \le 2 \cdot 10^5$), one line per game.

출력

For each game, print the number of blue balls necessary for the chance of Alice's victory to be as close as possible to 50ドル\%$ in a separate line in the same order as in the input file.

제한

힌트