가오카오

Roundgod는 가오카오(전국 통일 대학 입학 시험)를 앞두고 있고, 목표 대학은 저장대학이다. 그는 수학을 공부하다가 파스칼 삼각형에 관한 흥미로운 문제를 발견한다.

파스칼 삼각형의 정의는 다음과 같다.

파스칼 삼각형의 각 행에서 첫 번째 원소와 마지막 원소는 $1$이고, $n$번째 행의 $m$번째 원소는 $n-1$번째 행의 $m$번째 원소와 $m-1$번째 원소의 합과 같다. 다음은 5단계 파스칼 삼각형의 예이다.

$1$ $1\quad 1$ $1 \quad2\quad 1$ $1 \quad3 \quad3\quad 1$ $1 \quad4\quad 6\quad 4 \quad1$

이 과제에서 Roundgod는 파스칼 삼각형의 $126$번째 행에 있는 원소 중 홀수가 몇 개인지 계산해야 한다.

이 문제를 푼 뒤 Roundgod는 더 어려운 버전을 떠올린다. 그는 비슷한 질문을 여러 개 준비했지만 행 번호가 더 커진다. 파스칼 삼각형의 $k$번째 행에 있는 원소 중 홀수가 몇 개인지 계산하시오.

여러 개의 테스트 케이스가 주어진다. 입력의 첫 줄에는 정수 $T$ ($1 \le T \le 500$)가 주어지며, 이는 테스트 케이스의 수를 나타낸다. 각 테스트 케이스에 대해:

첫째 줄이자 유일한 줄에는 정수 K$$(K\leq 10^{18})가 주어지며, 이는 파스칼 삼각형에서 구하려는 행 번호를 나타낸다.

각 테스트 케이스에 대해 $k$번째 행에 있는 홀수의 개수를 출력한다.