Question

Minimum Number of Ones

2

6

8

3

4

Your teacher gave you an assignment - given an integer N, construct a binary string B = b_{1}b_{2}b_{3}…b_{N} of length N such that: max(b_{i}, b_{i+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.

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.