401937: GYM100589 E Count Distinct Sets

Alice writes a permutation P₁, P₂, P₃, ... P_N of [1, 2, 3, ...N]. A permutation 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 at-least one of the ‘amusing’ permutations.

You have to find how many distinct S_i exist for i  =  1 to N.

First line contains T, the number of test cases. Each test case consists of N in single line.

For each test case, print the required answer in one line.

Constraints

• 1 ≤ T ≤ 10⁴
• 1 ≤ N ≤ 10¹⁸

2
2
3

2
2

Example 1. Only ‘amusing’ permutations is [1, 2]. [2, 1] is not an ‘amusing’ permutation because P₂ < P_2 / 2.

S₁ is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations. Similarly S₂ is defined as {2}.

Therefore 2 distinct sets are possible ie. {1} and {2}.

Example 2. All ‘amusing’ permutations are: [1, 2, 3] and [1, 3, 2].

S₁ is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations. Similarly S₂ is defined as {2, 3} and S₃ is also defined as {2, 3}.

So a total of 2 distinct sets {1} and {2, 3} are possible.