CF818F.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.

伊万正在开发自己的电脑游戏。目前，他试图为游戏创建一些关卡。但首先，对于每个关卡，他都需要绘制一张图来表示该关卡的结构。

伊万决定：表示第 $i$ 关的图应恰好包含 $n_i$ 个顶点，且所有边均为无向边。在构造该图时，伊万特别关注一类特殊的边——桥（bridge）。连接两个顶点 $u$ 和 $v$ 的边被称为桥，当且仅当该边属于 $u$ 与 $v$ 之间每一条路径（即：若删除该边，则 $u$ 与 $v$ 将位于不同的连通分量中）。对于每一关，伊万希望构造出一张图，使得其中至少一半的边是桥。同时，他还希望使每张图的边数尽可能多。

因此，伊万交给你的任务是：给定 $q$ 个整数 $n_1,\,n_2,\,\dots,\,n_q$，对每个 $i$，求出一个含 $n_i$ 个顶点的图所能拥有的最大边数，要求其中至少一半的边是桥。注意：图中不允许存在重边或自环。

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·109) — the number of vertices in i-th graph.

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

输入文件的第一行包含一个正整数 $q$（$1 \le q \le 100\,000$）—— 表示 Ivan 需要构造的图的数量。

接下来是 $q$ 行，其中第 $i$ 行包含一个正整数 $n_i$（$1 \le n_i \le 2 \cdot 10^9$）—— 表示第 $i$ 个图的顶点数。

注意：在 hack 中，必须使用 $q = 1$。

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

输出 $q$ 个数，其中第 $i$ 个数必须等于第 $i$ 个图中边数的最大值。

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.

在第一个例子中，可以构造以下图：

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。