Collatz

In the process to solve the Collatz conjecture, better known as the 3n + 1 problem, Carl created a physical model with wood and ropes. A wooden bar contains a hole for every natural number from 1 to infinity from left to right. For every even number m there is a rope connecting the mth hole with hole m/2. For every odd number n there is a rope connecting the nth hole with hole 3n + 1.

For an important conference where Carl plans to elaborate on his results, he wants to bring his structure, but it is too large to fit in his bag. So he decided to saw off the part of the bar containing the first N holes only. How many ropes will he need to cut?

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:

• One line with an integer N, satisfying 0 ≤ N ≤ 109.

For every test case in the input, the output should contain a single number, on a single line: the number of ropes that need to be cut.