Ivan 正在开发他自己的电脑游戏。现在他尝试为他的游戏创建一些关卡。但首先,他需要为每个级别绘制一个表示该级别结构的图表。
Ivan 决定图中应该正好有 ni 个顶点代表级别 i,并且边必须是双向的。在构建图时,Ivan 对称为桥的特殊边感兴趣。如果两个顶点 u 和 v 之间的边属于 u 和 v 之间的每条路径,则该边称为桥(如果我们删除这条边,这些顶点将属于不同的连通分量)。对于每个级别,Ivan 想要构建一个图,其中至少一半的边是桥。他还希望最大化每个构建图中的边数。
所以 Ivan 给你的任务是:给定 q 个数字 n1, n2, ..., nq,对于每个 i 来说,如果至少一半的边是桥,则告诉具有 ni 个顶点的图中的最大边数。请注意,图不能包含多条边或自环。
输入
输入文件的第一行包含一个正整数 q (1 ≤ q ≤ 100 000) — Ivan 需要构建的图的数量。
接下来是 q 行,第 i 行包含一个正整数 ni (1 ≤ ni ≤ 2·109) — 第 i 个图中的顶点数。
请注意,在 hacks 中你必须使用 q = 1。
输出
输出 q 个数,其中第 i 个数必须等于第 i 个图中的最大边数。
示例
输入 #1
3 3 4 6
输出 #1
2 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.