Number Game
Time limit1sMemory limit128 MB
For a given N, sum the trailing zero counts of N written in every base from 2 upward, which reduces to summing over divisors of N greater than 1 how many times each divides N.
- Level
Medium5 of 10
- Topics
- Number theory, Math, Brute force
- Solved
- No attempts yet
Problem
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.
Input
The first line contains the number of test cases T. Each of the next T lines contains one integer N.
Output
For each test case, print the value of the sum above on its own line.
Constraints
- 1 <= T <= 100,000
- 1 <= N <= 1,000