You are given Q queries and for each query, there is a Binary Tree with \(N\) vertices numbered 1 through N. For each \(i\) from \(2\) to \(N\), there is an edge between vertex \(i\) and vertex \(i/2\) (rounded down). Count number of paths such that bitwise AND of all nodes on that path is odd. A path will be considered valid if the number of nodes on that path is greater than 1.
Note: The value of the nodes is equal to the indices.

Input:
The first line of the input contains a single integer Q denoting the number of queries. The description of Q queries follows: A single line having the value of N.

Output:
For each query, print a single line containing one integer — the number of paths such that bitwise AND of all nodes on that path is odd.

Constraints:

\(1 \leq Q, N \leq 10^5\)