Boredom Buster (Hard)

Gillian is normally a very lively child. Most of the time she plays with her friends and tries to indulge in some mischief. But today is different. Gillian woke up with the flu, so she has to stay in bed, still and bored. To entertain her, her brother came up with the following game.

When Gillian has an integer $x$ greater than 1, she can split it into two positive integers $y$ and $z$ such that $x = y + z$. After this operation, her brother gives her $y \cdot z$ hazelnuts. However, not all pairs of $y$ and $z$ are valid. Gillian must follow some rules. These rules differ between the easy and hard subproblems, and they are listed in the problem specification section.

Numbers obtained from this operation can also be split. At the start of the game, Gillian has a single integer $n$. She performs a series of operations until she has $n$ copies of the number 1. What is the maximum number of hazelnuts she can win if she chooses her moves wisely?

Gillian can pick any integer $k$ with $1 < k \le x$ and split $x$ into $y = \lfloor x/k \rfloor$ and $z = x - \lfloor x/k \rfloor$.

The first line of the input contains an integer $t$ ($t \le 1000$), the number of test cases. Each test case is preceded by a blank line.

Each test case contains a single line with Gillian's initial integer $n > 1$. You may assume that $n \le 10^9$.

For each test case, output a single line with the maximum number of hazelnuts.