一只企鹅 Rocher 有 $$$n$$$ 棍子。对于所有 $$$1 \le i \le n$$$,他恰好有一根长度为 $$$i$$$ 的棍子。
他可以连接一些棍子。如果他连接两根长度为 $$$a$$$ 和 $$$b$$$ 的棍子,他会得到一根长度为 $$$a + b$$$ 的棍子。操作中使用的两根棍子从他的集合中消失,新连接的棍子出现在他的集合中并可用于下一个连接。
他想要创建最大数量的相同长度的木棍。不必使所有棍子都具有相同的长度,某些棍子可以具有其他长度。他能创造出多少根等长的木棍?
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) - 测试用例的数量。接下来的 $$$t$$$ 行包含测试用例的描述。
对于每个测试用例,唯一的行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{9}$$$)。
输出
对于每个测试用例,打印一个整数 - 问题的答案。
示例
输入 #1
4 1 2 3 4
输出 #1
1 1 2 2
注意
在第三种情况下,他可以连接两根长度为 $$$1$$$ 和 $$$2$$$ 的棍子,他将得到一根长度为 $$$3$$$ 的棍子。因此,他将有两根长度为 $$$3$$$ 的棍子。
在第四种情况下,他可以连接两根长度为 $$$1$$$ 和 $$$3$$$ 的棍子,他将得到一根长度为 $$$4$$$ 的棍子。之后,他将拥有三根长度为 $$$\{2, 4, 4\}$$$ 的棍子,因此两根棍子的长度相同,一根棍子的长度不同。