405436: GYM101962 H All-In

Concurrently to the 2018 ICPC Regionals, a huge international Poker event is being held in Soteropolis. Professional poker players from all around the world joined amateur Soteropolis players for a weekend of poker.

Two poker players in the event can join to play a head-to-head all-in game of poker. The organization of the event imposed a predetermined restriction $$$n$$$ on the number of chips a player can have during a game. The number of chips the two players have can be denoted by a pair of integers $$$(x, y)$$$. In a valid game, $$$x, y$$$ should be between $$$1$$$ and $$$n$$$. Also, $$$x + y$$$ shouldn't exceed $$$n$$$.

An all-in game of poker is a game where players will always bet $$$min(x, y)$$$. In each turn, the winner will get $$$min(x, y)$$$ chips and the loser will lose as many chips. If after a turn one of the players have no chips, the game is considered finished. Otherwise, the game will continue.

Unfortunately, there are scenarios where the game can last forever. For example, in a game where the players have $$$(2, 1)$$$, if the player with less chips always win, the game will never end. The organization of the event want to prohibit every game that may possibly last forever.

The games which will for sure end in a finite number of turns are called finite. Even finite games may take a long time to finish. Let $$$t(x, y)$$$ be the maximum time a finite game with chips $$$(x, y)$$$ can last.

Your task is to compute the sum of $$$t(x, y)$$$ for every distinct $$$(x, y)$$$ that represents a valid finite game, given the predetermined restriction $$$n$$$.

Notice that $$$(x, y) \neq (y, x)$$$ if $$$x \neq y$$$. Also notice that an initially valid game will remain valid, even if it lasts forever.

The input contains $$$T$$$ ($$$1 \leq T \leq 10^4$$$) testcases. The following $$$T$$$ lines contains the descriptions of each testcase.

The only line of a testcase description contains an integer $$$n$$$ ($$$2 \leq n \leq 10^{16}$$$) – the pretedermined restriction on the number of chips during a game.

For each testcase, output a single integer in a line – the sum of $$$t(x, y)$$$ for every finite valid game.

It is guaranteed that these numbers will fit into a 64-bit signed integer.

4
2
3
4
7

1
1
6
7