Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

A. Хитрая сумма
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этой задаче вам требуется найти сумму всех целых чисел от 1 до n, причём степени двойки нужно учитывать в сумме со знаком минус.

Например, при n = 4 сумма равна:  - 1 - 2 + 3 - 4 =  - 4, поскольку 1, 2 и 4 являются 20, 21 и 22 соответственно.

Вычислите ответ для t значений n.

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

В первой строке ввода записано число t (1 ≤ t ≤ 100) — количество чисел, для которых вам нужно вычислить запрашиваемую сумму.

В каждой из следующих t строк находится по одному целому числу n (1 ≤ n ≤ 109).

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

Для каждого из t чисел n выведите значение искомой суммы.

Примеры
Входные данные
2
4
1000000000
Выходные данные
-4
499999998352516354
Примечание

Первый пример разобран в условии задачи.