Total Collatz Steps

Given a positive integer N, compute the total number of steps required to reduce every integer from 1 to N to 1 using the Collatz sequence.

The Collatz sequence is defined as follows:

• If n = 1, the process stops.
• If n is even, the next number is \(\frac{n}{2}\).
• If n is odd and greater than 1, the next number is \(3n+1\).

For each integer i in the range [1, N], let \(f(i)\) be the number of steps needed to reduce i to 1. Your task is to compute the sum: \[ S = \sum_{i=1}^{N} f(i) \]

You will be given multiple test cases. For each test case, output the computed total on a separate line.

inputFormat

The first line of input contains a single integer T, the number of test cases.

Each of the following T lines contains a single integer N.

All input is read from stdin.

outputFormat

For each test case, output a single line containing the total number of steps required for all numbers from 1 to N to be reduced to 1.

All output should be written to stdout.

## sample

1
3

8

</p>