По заданному значению n вычислите сумму НОК(1, n) + НОК(2, n) + .. + НОК(n, n), где НОК(i, n) обозначает Наименьшее Общее Кратное чисел i и n.

Входные данные

Первая строка содержит количество тестов t (1 ≤ t ≤ 300000). Каждая из следующих t строк содержит одно целое число n (1 ≤ n ≤ 106).

Выходные данные

Выведите t строк, каждая из которых содержит требуемую сумму.