{"problem":{"name":"E. Count Distinct Sets","description":{"content":"Alice writes a permutation P1, P2, P3, ... PN of [1, 2, 3, ...N]. A permutation that follows the condition: Pi > Pi / 2 for all i  =  2 to N, is assumed to be an ‘amusing’ permutation. Note that  /  ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10058E"},"statements":[{"statement_type":"Markdown","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## Input\n\nFirst line contains T, the number of test cases. Each test case consists of N in single line.\n\n## Output\n\nFor each test case, print the required answer in one line.*Constraints*   1 ≤ T ≤ 104  1 ≤ N ≤ 1018 \n\n[samples]\n\n## Note\n\nExample 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10058E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}