Count Distinct Sets

All submissions for this problem are available.
Alice writes a permutation P_{1}, P_{2}, P_{3}, … P_{N} of [1, 2, 3, … N] that follows the condition:
P_{i} > P_{i/2} for all i = 2 to N, is assumed to be an ‘amusing’ permutation.
Note that ‘/’ denotes integer division.
Alice wrote down all ‘amusing’ permutations on a sheet of paper.
For each number from i = 1 to N, she defines a set S_{i}. A number j belongs to S_{i} if number i was at j^{th} position in atleast one of the ‘amusing’ permutations.
You have to find how many distinct S_{i} exist for i = 1 to N.
Input
First line contains T, the number of test cases. Each test case consists of N in single line.
Output
For each test case, print the required answer in one line.
Constraints
 1 ≤ T ≤ 10000
 1 ≤ N ≤ 10^{18}
Example
Input: 2 2 3 Output: 2 2
Explanation
Example 1.
Only ‘amusing’ permutations is:
[1, 2].
[2, 1] is not an ‘amusing’ permutation because P_{2} < P_{2/2}.
S_{1} is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations.
Similarly S_{2} is defined as {2}.
Therefore 2 distinct sets are possible ie. {1} and {2}.
Example 2.
All ‘amusing’ permutations are:
[1, 2, 3]
[1, 3, 2]
S_{1} is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations.
Similarly S_{2} is defined as {2, 3} and S_{3} is also defined as {2, 3}.
So a total of 2 distinct sets {1} and {2,3} are possible.
Author:  tanmaysahay94 
Tags  tanmaysahay94 
Date Added:  2022015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 