{"raw_statement":[{"iden":"statement","content":"Alice writes a permutation P1, P2, P3, ... PN of [1, 2, 3, ...N]. A permutation that follows the condition:\n\nPi > Pi / 2 for all i  =  2 to N, is assumed to be an ‘amusing’ permutation. Note that  /  denotes integer division.\n\nAlice wrote down all ‘amusing’ permutations on a sheet of paper. For each number from i  =  1 to N, she defines a set Si. A number j belongs to Si if number i was at j’th position in at-least one of the ‘amusing’ permutations.\n\nYou have to find how many distinct Si exist for i  =  1 to N.\n\nFirst line contains T, the number of test cases. Each test case consists of N in single line.\n\nFor each test case, print the required answer in one line.\n\n*Constraints* \n\nExample 1. Only ‘amusing’ permutations is [1, 2]. [2, 1] is not an ‘amusing’ permutation because P2 < P2 / 2.\n\nS1 is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations. Similarly S2 is defined as {2}.\n\nTherefore 2 distinct sets are possible ie. {1} and {2}.\n\nExample 2. All ‘amusing’ permutations are: [1, 2, 3] and [1, 3, 2].\n\nS1 is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations. Similarly S2 is defined as {2, 3} and S3 is also defined as {2, 3}.\n\nSo a total of 2 distinct sets {1} and {2, 3} are possible.\n\n"},{"iden":"input","content":"First line contains T, the number of test cases. Each test case consists of N in single line."},{"iden":"output","content":"For each test case, print the required answer in one line.*Constraints*   1 ≤ T ≤ 104  1 ≤ N ≤ 1018 "},{"iden":"examples","content":"Input223Output22"},{"iden":"note","content":"Example 1. Only ‘amusing’ permutations is [1, 2]. [2, 1] is not an ‘amusing’ permutation because P2 < P2 / 2.S1 is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations. Similarly S2 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].S1 is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations. Similarly S2 is defined as {2, 3} and S3 is also defined as {2, 3}.So a total of 2 distinct sets {1} and {2, 3} are possible."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $. A permutation $ P = (P_1, P_2, \\dots, P_N) $ of $ \\{1, 2, \\dots, N\\} $ is *amusing* if $ P_i > P_{\\lfloor i/2 \\rfloor} $ for all $ i = 2, 3, \\dots, N $.  \n\nFor each $ i \\in \\{1, \\dots, N\\} $, define the set $ S_i \\subseteq \\{1, \\dots, N\\} $ as:  \n$$ S_i = \\{ j \\in \\{1, \\dots, N\\} \\mid \\exists \\text{ an amusing permutation } P \\text{ such that } P_j = i \\} $$\n\n**Constraints**  \n- $ 1 \\le T \\le \\text{some bound} $ (not specified, but irrelevant for formalism)  \n- For each test case: $ 1 \\le N \\le \\text{some bound} $ (not specified)  \n\n**Objective**  \nCompute the number of *distinct* sets $ S_i $ for $ i = 1 $ to $ N $.","simple_statement":"We are given a permutation of [1, 2, ..., N] called \"amusing\" if for all i from 2 to N:  \n**P[i] > P[i//2]** (integer division).\n\nWe define for each position i (from 1 to N), a set S_i:  \n→ S_i = { all numbers j such that j appears at position i in at least one amusing permutation }\n\nWe need to count **how many distinct sets S_i** exist among i = 1 to N.\n\n---\n\n### Simplified Statement:\n\nYou are given N.  \nConsider all permutations of [1, 2, ..., N] where every element is greater than its parent in a binary heap (i.e., P[i] > P[i//2] for i ≥ 2).  \nThese are called \"amusing\" permutations.\n\nFor each position i (1 to N), collect all numbers that ever appear at position i across all amusing permutations → call this set S_i.\n\nCount how many **different** S_i sets there are.\n\n---\n\n### Example:\n\n- N=2: Only [1,2] is amusing.  \n  S₁ = {1}, S₂ = {2} → 2 distinct sets.\n\n- N=3: Amusing perms: [1,2,3], [1,3,2]  \n  S₁ = {1}, S₂ = {2,3}, S₃ = {2,3} → 2 distinct sets.\n\n---\n\n### Goal:  \nFor each test case with N, output the number of distinct S_i sets.","has_page_source":false}