409793: GYM103743 J Balanced Tree

A binary tree $$$T$$$ is called super balanced if $$$T$$$ is empty or satisfies the following three conditions at the same time:

1. The left subtree of $$$T$$$ is super balanced.
2. The right subtree of $$$T$$$ is super balanced.
3. The number of nodes of the left subtree and the right subtree differs at most $$$1$$$.

Please calculate the number of super balanced trees consisting of $$$n$$$ nodes. Since the answer can be very large, just output the answer modulo $$$2^{64}$$$.

The first line contains a single integer $$$T$$$ ($$$1\le T\le 10^6$$$), indicating the number of test cases.

Each test case contains a single integer $$$n$$$ ($$$0 \le n < 2 ^{64}$$$), indicating the number of nodes in the tree.

For each test case, output an integer in a single line indicating the number of super balanced trees consisting of $$$n$$$ nodes.

2
2
3

2
1