In the heart of 17th-century Dhaka, the construction of the Lalbagh Fort is underway. To secure the southern gate, the royal architect has designed a complex locking mechanism consisting of $$$n$$$ interlocking brass gears.
The total number of gears, $$$n$$$, is determined by the number of days $$$k$$$ spent on the gate's construction. On the $$$1$$$st day, $$$1$$$ gear was installed. On each subsequent day, the builders added the next consecutive odd number of gears ($$$3$$$ on the second day, $$$5$$$ on the third, and so on).
Each gear in the system is unique, numbered $$$1, 2, \ldots, n$$$. A gear numbered $$$x$$$ has exactly $$$x$$$ teeth. For the mechanism to rotate without friction, the architect only selects gears that are mechanically stable.
The stability of a gear is determined by its rotational partitions. A gear with $$$x$$$ teeth can be partitioned into $$$m$$$ equal-sized segments, where $$$m$$$ is any integer that divides $$$x$$$. A gear is mechanically stable only if the number of ways to partition it into segments containing an even number of teeth is perfectly balanced by the number of ways to partition it into segments containing an odd number of teeth.
For example, consider gear $$$6$$$. It can be partitioned into segments of size $$$1$$$, $$$2$$$, $$$3$$$, or $$$6$$$.
Since there are exactly two even-sized partition options and two odd-sized partition options, gear $$$6$$$ is stable.
Given the number of construction days $$$k$$$, calculate how many mechanically stable gears are in the Lalbagh gate.
The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^6)$$$ — the number of test cases.
Each of the next $$$t$$$ lines contains a single integer $$$k$$$ $$$(1 \le k \le 2^{32})$$$ — the number of construction days.
For each test case, output a single integer — the number of mechanically stable gears among all gears numbered from $$$1$$$ to $$$n$$$.
412510
01625
