A person A has n toys, numbered from 1 to n. He will give some of the toys to his
children X and Y. X and Y have preference for toys no. a and b respectively [a and b are distinct]. But a,b are not known beforehand.
Now A has to make/propose some possible combinations of toys such that when X and Y
announce any value of a and b, there must exist 2 distinct, disjoint proposed combinations C and D such that C contains toy no. ‘a’ while D contains toy no. ‘b’ (they may or may not contain other toys). [See explanation of sample test cases for more clearity]
Your task is to find minimum no. of combinations/groups which A must propose.
First line of input contains an integer ‘t’, representing number of test cases.
Each of next t lines contain an integer ‘n’, representing total number of toys.
For each test case, output minimum number of proposed groups.
Explanation of sample test cases:
For second case, consider 6 toys=1,2,3,4,5,6.
If we plan 5 combinations as (1,2), (3,4), (5,6), (1,3,5), (2,4,6) , then this scheme meets all the criterions.
E.g. if (a,b)= (1,2) [i.e. if X wants toy 1 and Y wants toy 2], we can choose combinations[(1,3,5)] and
[(2,4,6)]. These combinations don’t have any toy in common[hence disjoint]. (1,3,5) has toy no.1 while
(2,4,6) has toy no. 2. Similarly if (a,b)= (1,3), then we can choose two combinations [(1,2)] and [(3,4)].
Similar pair of combinations can be found for each pair (a,b). There can be more ways to do this task,
but you cannot do this task in less than 5 proposed combinations. Hence the answer is 5.
For third case, consider toys=1,2,3,4
If we plan 4 combinations as (1), (2), (3), (4), then this scheme meets all the criterions. E.g if (a,b)=(1,2),
then we can choose combinations (1) and (2). Similar pair of combinations can be found for each pair
(a,b). There can be more ways to do this task, but you cannot do this task in less than 4 combinations.
Hence the answer is 4.