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
Well if you thought answer is n/2 then you did a mistake because of the given sample (i did the same mistake),
let’s solve now for n=8 then {1,2,3,4} {5,6,7,8} now 1 has only 2,3,4 left so we can replace like
{1,4,5,6} {2,3,7,8} and now see 1 has only 4 left and 8 left with 7 and 6 with 5 so
{1,5,7,2} {8,3,4,6} so if you see we just need log2(n) if n=power of 2 otherwise log2(n)+1.
First split the group in two equal halves, each with size (n/2).Now all the people from first half have met with those from second half and vice versa. So, we only need to consider these halves individually. That is, our answer would be 1 + no. of sittings reqd. for the two halves.
So, we need solution for (n/2). If (n/2) is odd, increment it by one for the bigger half. (Eg. n=5, h1=3,h2=2,consider h1).