Number Game

Changyeong invented a quiet number game. First choose a positive integer N. Then write N in base 2, base 3, base 4, and so on, and add up the number of consecutive zeroes at the end of each representation.

For example, when N = 5, its representations are 101 in base 2, 12 in base 3, 11 in base 4, 10 in base 5, and 5 in every base greater than 5. Therefore the total is 1.

More formally, let f(N, b) be the number of consecutive trailing zeroes when N is written in base b. Compute

\[ \sum_{b=2}^{\infty} f(N, b) \]

for each given N.

The first line contains the number of test cases T. Each of the next T lines contains one integer N.

For each test case, print the value of the sum above on its own line.

• 1 <= T <= 100,000
• 1 <= N <= 1,000