숫자 게임
시간 제한1초메모리 제한128 MB
주어진 N에 대해 밑을 2 이상으로 바꿔가며 표기했을 때 끝에 붙는 0의 개수를 모두 더하는데, 이는 N의 1보다 큰 각 약수가 N을 몇 번 나누는지를 합산하는 문제로 귀결됩니다.
문제
창영이는 조용한 숫자 게임을 생각해 냈다. 먼저 양의 정수 N을 정한다. 그리고 N을 2진법, 3진법, 4진법, ... 으로 차례대로 나타내며, 각 표현의 마지막에 연속해서 붙어 있는 0의 개수를 모두 더한다.
예를 들어 N = 5라면 2진법에서는 101, 3진법에서는 12, 4진법에서는 11, 5진법에서는 10, 6 이상의 진법에서는 5로 나타난다. 따라서 합은 1이다.
정확히는 f(N, b)를 N을 b진법으로 나타냈을 때 끝에 연속해서 붙는 0의 개수라고 하자. 주어진 각 N에 대해 다음 값을 구하라.
\[ \sum_{b=2}^{\infty} f(N, b) \]
입력
첫째 줄에 테스트 케이스의 수 T가 주어진다. 다음 T개의 줄에는 정수 N이 하나씩 주어진다.
출력
각 테스트 케이스마다 위 합의 값을 한 줄에 출력한다.
제한
- 1 <= T <= 100,000
- 1 <= N <= 1,000