Nguồn đề: https://codeforces.com/contest/1371/problem/A

Hải có n cái gậy, lần lượt có độ dài là 1, 2, 3, ... n . Hải có thể nối các gậy lại với nhau, khi nối 2 gậy có độ dài a và b lại với nhau, Hải có được 1 cái gậy có độ dài là a + b. Khi gắn như vậy Hải không thể dùng 2 gậy cũ nữa thay vào đó Hải có thêm một gậy mới với độ dài a + b vừa tạo được.

Hải muốn tạo được nhiều gậy bằng nhau nhất có thể. Không nhất thiết là tất cả các gậy phải bằng nhau. Đố các bạn Hải có thể tạo được tối đa bao nhiêu cái gậy bằng nhau ?

Input

Dòng 1: t (1 ≤ t ≤ 1000) - số lượng test case. Dòng 1: n ~(1 ≤ n ≤ 10^9)~ - số lượng gậy Hải có.

Output

Với mỗi test case in ra số lượng tối đa các gậy có độ dài bằng nhau mà Hải có thể tạo được.

Sample Input

4
1
2
3
4

Sample Output

1
1
2
2