Collatz

Time limit1sMemory limit128 MB

Summary

For each N, count how many ropes of the Collatz graph connect holes in 1..N to holes outside 1..N.

Level: Medium5 of 10
Topics: Math, Number theory, Implementation
Solved: No attempts yet

Problem

While studying the Collatz conjecture, better known as the 3n + 1 problem, Carl built a physical model out of wood and rope. A wooden bar has one hole for every natural number from 1 to infinity, ordered from left to right. For every even number $m$ there is a rope connecting hole $m$ with hole $m/2$ . For every odd number $n$ there is a rope connecting hole $n$ with hole $3n + 1$ .

Carl wants to bring this structure to an important conference where he plans to present his results, but it is too large to fit in his bag. So he decided to saw off the bar so that only the first $N$ holes remain. How many ropes will he need to cut?

Input

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

One line with an integer $N$ ( $0 \le N \le 10^9$ ).

Output

For each test case, output a single line containing the number of ropes that need to be cut.

Examples3

Example 1
Input
```
3
12
240
3600
```
Expected output
```
10
200
3000
```
Example 2
Input
```
1
0
```
Expected output
```
0
```
Example 3
Input
```
1
1
```
Expected output
```
2
```