{"raw_statement":[{"iden":"problem statement","content":"You are given non-negative integers $q,L,R\\;(q \\in { 0,1}, \\; L \\leq R)$. Consider a set $S$ that satisfies all of the following conditions.\n\n*   $S$ consists of distinct integers between $L$ and $R$, inclusive.\n*   If $a \\in S, \\; b \\in S, \\; a \\neq b$, then $a$ and $b$ differ in at least two digits in binary representation. More formally, there exist at least two non-negative integers $i$ such that $\\left\\lfloor\\frac{a}{2^i}\\right\\rfloor$ and $\\left\\lfloor\\frac{b}{2^i}\\right\\rfloor$ have different parities.\n*   Among those satisfying the above two conditions, the number of elements is maximum.\n\nIf $q=0$, find the number of elements in such a set $S$.  \nIf $q=1$, construct one such set $S$.\nFor each input file, solve $T$ test cases."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 2 \\times 10^5$\n*   $0 \\leq q \\leq 1$\n*   $0 \\leq L \\leq R \\leq 10^{18}$\n*   The sum of $q(R-L)$ over all test cases is at most $5\\times 10^6$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach case is given in the following format:\n\n$q$ $L$ $R$"},{"iden":"sample input 1","content":"3\n1 0 3\n0 1 2\n1 213 213"},{"iden":"sample output 1","content":"1001\n2\n1\n\nIn the first test case, $S={0,3}$ satisfies the conditions. $S={1,2}$ also satisfies the conditions, so it is correct as well.  \nIn the second test case, the only $S$ that satisfies the conditions is ${1,2}$, whose number of elements is $2$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}