{"trustable":false,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Description","value":{"format":"HTML","content":"\t\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n\t MathJax.Hub.Config({\n\t extensions: [\"tex2jax.js\"],\n\t jax: [\"input/TeX\", \"output/SVG\"],\n\t tex2jax: {\n\t inlineMath: [ [\u0027$\u0027,\u0027$\u0027], [\"\\\\(\",\"\\\\)\"] ],\n\t displayMath: [ [\u0027$$\u0027,\u0027$$\u0027], [\"\\\\[\",\"\\\\]\"] ],\n\t processEscapes: true\n\t },\n\t });\n\t\u003c/script\u003e\n\t\u003cscript type\u003d\"text/javascript\"\n\t src\u003d\"https://cdn.staticfile.org/mathjax/2.7.0/MathJax.js\"\u003e\n\t\u003c/script\u003e\n \n \u003cp\u003e After this winter holiday, My little brother Little Gyro is about to take a math exam at school. As he is very confident, he believes there is no need for a review. \u003c/p\u003e \n \u003cp\u003e Little Gyro\u0027s father, Mr.Potato, is nervous about Little Gyro\u0027s attitude, so he gives Little Sub a task to do. To his surprise, Little Gyro finishes the task quickly and perfectly and even solves the most difficult problem in the task. \u003c/p\u003e \n \u003cp\u003e Mr.Potato trys to find any possible mistake on the task paper and suddenly notices an interesting problem. It\u0027s a problem related to Pascal\u0027s Triangle. \u003c/p\u003e\n \u003cdiv style\u003d\"text-align: center;\"\u003e \n \u003cimg height\u003d\"384\" SRC\u003d\"CDN_BASE_URL/ae3f3b784985cd4f970e7f5411187854?v\u003d1553225279\" alt\u003d\"“math”/\"\u003e \n \u003c/div\u003e \n \u003cp\u003e The definition of Pascal\u0027s Triangle is given below: \u003c/p\u003e \n \u003cp\u003e The first element and the last element of each row in Pascal\u0027s Triangle is $1$, and the $m$-th element of the $n$-th row equals to the sum of the $m$-th and the $(m-1)$-th element of the $(n-1)$-th row. \u003c/p\u003e \n \u003cp\u003eAccording to the definition, it\u0027s not hard to deduce the first few lines of the Pascal\u0027s Triangle, which is:\u003cbr\u003e $1$\u003cbr\u003e $1$ $1$\u003cbr\u003e $1$ $2$ $1$\u003cbr\u003e $1$ $3$ $3$ $1$\u003cbr\u003e $1$ $4$ $6$ $4$ $1$\u003cbr\u003e ......\u003cbr\u003e \u003c/p\u003e \n \u003cp\u003e In the task, Little Gyro is required to calculate the number of odd elements in the 126th row of Pascal\u0027s Triangle. \u003c/p\u003e \n \u003cp\u003e Mr.Potato now comes up with a harder version of this problem. He gives you many queries on this problem, but the row number may be extremely large. For each query, please help Little Sub calculate the number of odd elements in the $k$-th row of Pascal\u0027s Triangle. \u003c/p\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003e There are multiple test cases. The first line of the input contains an integer $T$ ($1 \\le T \\le 500$), indicating the number of test cases. For each test case: \u003c/p\u003e \n \u003cp\u003e The first and only line contains an integer $k$ ($1 \\le k \\le 10^{18}$), indicating the required row number in Pascal\u0027s Triangle. \u003c/p\u003e \n \u003ch4"}},{"title":"Output","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003e For each test case, output the number of odd numbers in the $k$-th line. \u003c/p\u003e \n \u003ch4"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cpre\u003e3\n3\n4\n5\n\u003c/pre\u003e \n \u003ch4"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cpre\u003e2\n4\n2\n\u003c/pre\u003e \n "}}]}