Question
Minimum Number of Ones
Your teacher gave you an assignment - given an integer N, construct a binary string B = b1b2b3…bN of length N such that: max(bi, bi+1) = 1 for every i from 1 to N - 1.
What is the minimum number of 1's such a binary string can contain?
Note: A binary string is a string consisting of only the digits 0 and 1.
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case contains a single integer N - The length of binary string you'd like to construct.
Constraints
1 ≤ T ≤ 1000
2 ≤ N ≤ 1000
Each test case contains a single integer N - The length of binary string you'd like to construct.
Constraints
1 ≤ T ≤ 1000
2 ≤ N ≤ 1000
Output
For each test case, output on a new line the minimum number of 1's required to complete the assignment.
Example
Input
2
6
8
Output
3
4
Explanation
Test case 1: One possible binary string is 010101. This has three 1's, and it can be verified that the maximum of any two adjacent characters is 1. Achieving this with less than three 1's is not possible.
Test case 2: One possible binary string is 10101010. This has four 1's, and it can be verified that the maximum of any two adjacent characters is 1.
2
6
8
Output
3
4
Explanation
Test case 1: One possible binary string is 010101. This has three 1's, and it can be verified that the maximum of any two adjacent characters is 1. Achieving this with less than three 1's is not possible.
Test case 2: One possible binary string is 10101010. This has four 1's, and it can be verified that the maximum of any two adjacent characters is 1.