Дано додатне ціле число . Обчисліть значення функції :

Тут позначає цілочисельне ділення.
Оскільки може бути дуже великим, виведіть .
У першому рядку знаходиться число — кількість тестових випадків. Кожен з наступних рядків містить значення для відповідного тестового випадку.
Гарантується, що 1 \leq T \leq 50, 1 \leq N \leq 10^9.
Виведіть рядків, де -й рядок містить відповідь для -го тестового випадку.
Приклад 1