A vintage telegraph exchange labels every switchboard panel with a positive integer ID. Each panel's ID is displayed as a row of toggle switches showing the ID's binary representation with no leading OFF switch (the leftmost switch is always ON). A panel is called balanced if exactly half of its toggle switches are ON and exactly half are OFF.
The exchange's archivist wants to audit several ranges of panels. For each audit you are given a limit n, and must report how many panel IDs from 1 to n (inclusive) are balanced.
The first line contains a single integer q, the number of audits.
Each of the next q lines contains a single integer n, the upper limit for that audit.
Output q lines. The i-th line must contain the number of balanced panel IDs in [1, n_i] for the i-th audit.
Example 1
Input
1 6
Expected
1
Explanation
Checking IDs 1 through 6 in binary (1, 10, 11, 100, 101, 110), only 2 ("10") has an equal number of ON and OFF switches (one of each), so the answer is 1.
Example 2
Input
2 1 15
Expected
0 4
Explanation
For n=1 the only ID is 1 ("1"), which has 1 ON and 0 OFF switches, so no balanced IDs exist and the answer is 0. For n=15, the balanced IDs are 2 ("10"), 9 ("1001"), 10 ("1010"), and 12 ("1100"), giving an answer of 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →