PROGRAMMING:Little Gyro's Winter Homework
After this winter holiday, 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.
Little Gyro's father, Mr.Potato, is very anxious about Little Gyro's attitude, so he selects some math problems from Little Gyro's winter homework and gives Little Gyro 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.
Mr.Potato tries to find any possible mistake on the task paper and suddenly notices an interesting problem. It's a problem related to Pascal's Triangle.
The definition of Pascal's Triangle is given below:
The first element and the last element of each row in Pascal's 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.
According to the definition, it's not hard to deduce the first few lines of the Pascal's Triangle, which is:
```
one
1 1
1 2 1
1 3 3 1
1 4 6 4 1
......
```
In the task, Little Gyro is required to calculate the number of odd elements in the 126th row of Pascal's Triangle.
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 Gyro calculate the number of odd elements in the $$k$$-th row of Pascal's Triangle.
### Input Specification:
There are multiple test cases. The first line of the input contains an integer $$ T$$ (1 ≤ $$T$$ ≤ 500), indicating the number of test cases. For each test case:
The first and only line contains an integer $$k$$ (1 ≤ $$k$$ ≤ $$10^{18}$$), indicating the required row number in Pascal's Triangle.
### Output Specification:
For each test case, output the number of odd numbers in the $$k$$-th line.
### Sample Input:
```in
three
three
four
five
```
### Sample Output:
```out
two
four
two
```
### Hint:
In the first sample, the third line of the Pascal's Triangle contains two odd numbers: “1” and “1”.
In the second sample, the fourth line of the Pascal's Triangle contains four odd numbers: “1”, “3”, “3” and “1”.
And the answer of the third sample is same as the first sample.
answer：If there is no answer, please comment
Little Gyro's father, Mr.Potato, is very anxious about Little Gyro's attitude, so he selects some math problems from Little Gyro's winter homework and gives Little Gyro 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.
Mr.Potato tries to find any possible mistake on the task paper and suddenly notices an interesting problem. It's a problem related to Pascal's Triangle.
The definition of Pascal's Triangle is given below:
The first element and the last element of each row in Pascal's 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.
According to the definition, it's not hard to deduce the first few lines of the Pascal's Triangle, which is:
```
one
1 1
1 2 1
1 3 3 1
1 4 6 4 1
......
```
In the task, Little Gyro is required to calculate the number of odd elements in the 126th row of Pascal's Triangle.
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 Gyro calculate the number of odd elements in the $$k$$-th row of Pascal's Triangle.
### Input Specification:
There are multiple test cases. The first line of the input contains an integer $$ T$$ (1 ≤ $$T$$ ≤ 500), indicating the number of test cases. For each test case:
The first and only line contains an integer $$k$$ (1 ≤ $$k$$ ≤ $$10^{18}$$), indicating the required row number in Pascal's Triangle.
### Output Specification:
For each test case, output the number of odd numbers in the $$k$$-th line.
### Sample Input:
```in
three
three
four
five
```
### Sample Output:
```out
two
four
two
```
### Hint:
In the first sample, the third line of the Pascal's Triangle contains two odd numbers: “1” and “1”.
In the second sample, the fourth line of the Pascal's Triangle contains four odd numbers: “1”, “3”, “3” and “1”.
And the answer of the third sample is same as the first sample.
answer：If there is no answer, please comment