За даним значеннням $n$ обчислыть суму $НСК$($1$, $n$) + $НСК$($2$, $n$) + .. + $НСК$($n$, $n$), де $НСК$($i$, $n$) означає Найменше Спільне Кратне чисел $i$ і $n$.

Вхідні дані

Перший рядок містить кількість тестів $t$ ($1$ ≤ $t$ ≤ $300000$). Кожен із наступних $t$ рядків містить одне ціле число $n$ ($1$ ≤ $n$ ≤ $10^6$).

Вихідні дані

Виведіть $t$ рядків, кожен з яких містить потрібні суму.