Нулі всюди

Вхідні дані

Перший рядок містить одне ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — кількість тестових випадків.

Єдиний рядок кожного тестового випадку містить одне ціле число $n$ $(1 \leq n \leq 1 0^{6})$ (1 \le n \le 10^6).

Гарантується, що сума $n$ по всіх тестах не перевищує $1 0^{6}$ 10^6.

Для кожного тестового випадку виведіть одне ціле число — значення суми.

Приклад 1

Loading

У першому тестовому випадку число $1$ не має нулів у жодній системі числення, тому відповідь дорівнює $0$ .

У другому тестовому випадку відповідь дорівнює $5$ :

Основа $1$ дає $0$ .
Основа $2$ : $1 = (1)_{2}$ 1=(1)_2, $2 = (10)_{2}$ 2=(10)_2, $3 = (11)_{2}$ 3=(11)_2, $4 = (100)_{2}$ 4=(100)_2, і маємо $0 + 1 + 0 + 2 = 3$ 0+1+0+2=3 нулі.
Основа $3$ : лише $3 = (10)_{3}$ 3=(10)_3 містить нуль, отже, $1$ нуль.
Основа $4$ : лише $4 = (10)_{4}$ 4=(10)_4 містить нуль, отже, $1$ нуль.

і маємо $0 + 3 + 1 + 1 = 5$ 0+3+1+1=5.

У третьому тестовому випадку відповідь дорівнює $11$ :

Основа $1$ дає $0$ .
Основа $2$ : $2 = (10)_{2}$ 2=(10)_2, $4 = (100)_{2}$ 4=(100)_2, $5 = (101)_{2}$ 5=(101)_2, $6 = (110)_{2}$ 6=(110)_2, і маємо $1 + 2 + 1 + 1 = 5$ 1+2+1+1=5 нулів.
Основа $3$ : $3 = (10)_{3}$ 3=(10)_3 та $6 = (20)_{3}$ 6=(20)_3, отже, $2$ нулі.
Основи $4, 5, 6, 7$ 4,5,6,7: лише $y = (10)_{y}$ y=(10)_y містить нуль, отже, по $1$ нулю в кожній, усього $4$ .

і маємо $0 + 5 + 2 + 4 = 11$ 0+5+2+4=11.

Підзадача $1$ ( $50$ балів): $(1 \leq \sum n \leq 2000)$ (1 \le \sum n \le 2000)
Підзадача $2$ ( $200$ балів): $(1 \leq \sum n \leq 1 0^{6})$ (1 \le \sum n \le 10^6)