You are given ID of different uni-directional highways in the ByteLand. The highways are quite mysterious. If you convert their IDs to a binary number then it means that the bit position where the value is $$0$$, those lanes are closed or else the lanes are open. Now for each highway, you need to count in how many ways the open lanes of the highway can be occupied.

Note: If none of the lanes are occupied then also it is counted as a way.

Input Format

First line of the input contains an integer \(T\), the number of test cases.
Next \(T \) lines contain an integer \(N \).

Output Format

Print \(T\) lines, $$i$$-th line contains the answer to the $$i$$-th test case.

Constraints

$$1 \le T \le 10^5$$
$$1 \le N \le 10^{18}$$