Codeforces Round 654 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

math

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Magical Sticks

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA penguin Rocher has $$$n$$$ sticks. He has exactly one stick with length $$$i$$$ for all $$$1 \le i \le n$$$.

He can connect some sticks. If he connects two sticks that have lengths $$$a$$$ and $$$b$$$, he gets one stick with length $$$a + b$$$. Two sticks, that were used in the operation disappear from his set and the new connected stick appears in his set and can be used for the next connections.

He wants to create the maximum number of sticks that have the same length. It is not necessary to make all sticks have the same length, some sticks can have the other length. How many sticks with the equal length he can create?

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Next $$$t$$$ lines contain descriptions of test cases.

For each test case, the only line contains a single integer $$$n$$$ ($$$1 \le n \le 10^{9}$$$).

Output

For each test case, print a single integer — the answer to the problem.

Example

Input

4 1 2 3 4

Output

1 1 2 2

Note

In the third case, he can connect two sticks with lengths $$$1$$$ and $$$2$$$ and he will get one stick with length $$$3$$$. So, he will have two sticks with lengths $$$3$$$.

In the fourth case, he can connect two sticks with lengths $$$1$$$ and $$$3$$$ and he will get one stick with length $$$4$$$. After that, he will have three sticks with lengths $$$\{2, 4, 4\}$$$, so two sticks have the same length, and one stick has the other length.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/16/2024 02:08:27 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|