Level Generation

题意翻译

对于 $n$ 个点 $m $ 条边的简单无向图，如果有至少 $ \lceil\frac{m}{2}\rceil$ 条边是桥，则这个图是 “绝妙的” 。$q \ \ (q\le 10^5)$ 次询问，求出 $x \ \ (x\le 2\times 10^9)$ 个点的 “绝妙的” 图中，最多有多少条边。

题目描述

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.

输入输出样例

输入样例 #1

3
3
4
6

输出样例 #1

2
3
6

说明

In the first example it is possible to construct these graphs: 1. $ 1-2 $ , $ 1-3 $ ; 2. $ 1-2 $ , $ 1-3 $ , $ 2-4 $ ; 3. $ 1-2 $ , $ 1-3 $ , $ 2-3 $ , $ 1-4 $ , $ 2-5 $ , $ 3-6 $ .