숫자 게임

창영이는 조용한 숫자 게임을 생각해 냈다. 먼저 양의 정수 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