Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Level Generation

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIvan 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.

Input

The first line of input file contains a positive integer *q* (1 ≤ *q* ≤ 100 000) — 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

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

Example

Input

3

3

4

6

Output

2

3

6

Note

In the first example it is possible to construct these graphs:

- 1 - 2, 1 - 3;
- 1 - 2, 1 - 3, 2 - 4;
- 1 - 2, 1 - 3, 2 - 3, 1 - 4, 2 - 5, 3 - 6.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/14/2018 14:30:09 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|