企鹅 Rocher 有 $n$ 根木棍。对每个整数 $i$（$1 \le i \le n$），他恰好有一根长度为 $i$ 的木棍。

他可以把一些木棍连接起来：如果连接两根长度分别为 $a$ 和 $b$ 的木棍，那么会得到一根长度为 $a+b$ 的新木棍。参与连接的两根木棍会从集合中消失，新木棍会加入集合，并且可以继续用于之后的连接操作。

Rocher 想要得到尽可能多根长度相同的木棍。注意：不要求让所有木棍长度都相同，允许剩余一些木棍长度不同。

请问他最多能得到多少根长度相同的木棍？

输入格式

第一行一个整数 $t$（$1 \le t \le 1000$），表示测试用例数量。

接下来 $t$ 行，每行一个整数 $n$（$1 \le n \le 10^9$），表示木棍数量以及初始长度集合为 ${1,2,\dots,n}$。

输出格式

对每个测试用例输出一行一个整数，表示答案。

样例

输入

4
1
2
3
4

输出

1
1
2
2

说明

• 当 $n=3$ 时，可以连接长度 $1$ 和 $2$，得到长度 $3$，此时有两根长度为 $3$ 的木棍。
• 当 $n=4$ 时，可以连接长度 $1$ 和 $3$，得到长度 $4$，此时木棍长度集合为 ${2,4,4}$，其中长度 $4$ 出现两次。