Legion#3934
Legion — the main organizational unit in the army of Ancient Rome. Throughout different eras, the size and formation of legions varied. The simplest formation was a straight line. To select three soldiers from a legion arranged in a line for reconnaissance, the following process was used: if there were more than three soldiers in the line, it was split into two parts. One part consisted of soldiers standing in even positions, and the other of those in odd positions. This procedure was repeated for all resulting lines until each contained no more than three soldiers. If exactly three soldiers remained, this group could be sent for reconnaissance.
Your task is to determine how many groups of three soldiers can be formed from the initial line.
The first line of the input contains a single number — the number of test cases (T \leq 10^4). Each of the following lines contains a single integer — the number of soldiers in the line (0 \leq N \leq 10^{18}).
For each test case, output a single integer on a separate line — the number of groups of three soldiers that can be formed from the initial line.
Example 1