{"problem":{"name":"Exactly Three Bits","description":{"content":"For a positive integer $X$, let $f(X)$ be the number of $1$s that appear when $X$ is represented in binary notation. For example, $6 = 110_{(2)}, \\ 11 = 1011_{(2)}, \\ 16 = 10000_{(2)}$, so $f(6) = 2, ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc161_b"},"statements":[{"statement_type":"Markdown","content":"For a positive integer $X$, let $f(X)$ be the number of $1$s that appear when $X$ is represented in binary notation. For example, $6 = 110_{(2)}, \\ 11 = 1011_{(2)}, \\ 16 = 10000_{(2)}$, so $f(6) = 2, \\ f(11) = 3, \\ f(16) = 1$.\nYou are given a positive integer $N$. Determine whether there is a positive integer $X$ less than or equal to $N$ such that $f(X) = 3$, and if so, find the maximum such $X$.\nThere are $T$ test cases to solve.\n\n## Constraints\n\n*   $1 \\leq T \\leq 10^5$\n*   $1 \\leq N \\leq 10^{18}$\n\n## Input\n\nThe input is given from Standard Input in the following format, where $N_i$ represents the value of $N$ in the $i$\\-th test case:\n\n$T$\n$N_1$\n$N_2$\n$\\vdots$\n$N_T$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc161_b","tags":[],"sample_group":[["4\n16\n161\n4\n1000000000000000000","14\n161\n-1\n936748722493063168\n\n*   For the first test case, $f(14) = 3, \\ f(15) = 4, \\ f(16) = 1$, so the maximum positive integer $X$ satisfying $X \\leq 16$ and $f(X) = 3$ is $14$.\n*   For the second test case, $f(161) = 3$, so the maximum positive integer $X$ satisfying $X \\leq 161$ and $f(X) = 3$ is $161$.\n*   For the third test case, $f(1) = 1, \\ f(2) = 1, \\ f(3) = 2, \\ f(4) = 1$, so there is no positive integer $X$ satisfying $X \\leq 4$ and $f(X) = 3$.\n*   As seen in the fourth test case, the input and output values may not fit in a 32-bit integer type."]],"created_at":"2026-03-03 11:01:14"}}