У математического отдела появились проблемы. Из-за огромного количества автоматизированных программ, которые просматривали их страницы, они решили разместить на своих веб-страницах свои научные статьи. Чтобы получить к ним доступ, необходимо показать свои умения - а именно решить математическую загадку.

Тем не менее, тест оказался трудным для аспирантов и даже для некоторых профессоров. Поэтому математическому отделу следует написать программу, которая решает эту задачу.

Задача, которую предлагают любому посетителю стартовой страницы факультета математики, заключается в следующем: по заданному натуральному n вычислить

где через [x] обозначено наибольшее целое, не большее x.

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

Первая строка содержит количество запросов t (t ≤ 106). Каждый запрос состоит из одного натурального числа n (1 ≤ n ≤ 106).

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

Для каждого n вывести в отдельной строке значение Sn.