A11010 | Level Generation

Ivan is developing his own computer game. Now he tries to create some levels for his game. But firstly for each level he needs to draw a graph representing the structure of the level.

Ivan decided that there should be exactly $n_{i}$ vertices in the graph representing level $i$ , and the edges have to be bidirectional. When constructing the graph, Ivan is interested in special edges called bridges. An edge between two vertices $u$ and $v$ is called a bridge if this edge belongs to every path between $u$ and $v$ (and these vertices will belong to different connected components if we delete this edge). For each level Ivan wants to construct a graph where at least half of the edges are bridges. He also wants to maximize the number of edges in each constructed graph.

So the task Ivan gave you is: given $q$ numbers $n_{1},n_{2},...,n_{q}$ , for each $i$ tell the maximum number of edges in a graph with $n_{i}$ vertices, if at least half of the edges are bridges. Note that the graphs cannot contain multiple edges or self-loops.

The first line of input file contains a positive integer $q$ ( $1<=q<=100000$ ) — the number of graphs Ivan needs to construct.

Then $q$ lines follow, $i$ -th line contains one positive integer $n_{i}$ ( $1<=n_{i}<=2·10^{9}$ ) — the number of vertices in $i$ -th graph.

Note that in hacks you have to use $q=1$ .

Output $q$ numbers, $i$ -th of them must be equal to the maximum number of edges in $i$ -th graph.