A party has been organised after the successful launching of Codechef Chapter at IIT Patna. There are a total of n people attending the party. Everyone wishes to talk and shake hand with each other atleast once. Which means, for every pair of people (i,j), there should be at least one hand-shake.

To ensure this, organisers decided to split n people into two groups each of size n/2 (n is guaranteed to be even). Each person in a group sits down calmly with all the persons of the other group and then shake hands. Note that in one particular sitting, a person shakes hand with the n/2 members of the other group.

You have to find the minimum number of sittings in which the objective can be achieved.

Input:

The first line contains an integer T denoting the number of test cases. T test cases follow. The only line of each test case contains an integer N denoting the number of persons in the party.

Output:

For each test case print a single integer K which denotes the minimum number of sittings that should be conducted.

Constraints

1 ≤ T ≤ 10

2 ≤ N ≤ (10^5)$

N is even

Can anyone tell the approach to solve this, please, Problem Code: ANWCC01