题目描述

给出一个 $n$，求出从 $1$ 到 $n$ 的和，但是其中每当遇到一个数是 $2$ 的整数次幂时，就要变加为减。

例如输入 $n=4$，那么计算算式为 $-1-2+3-4=-4$，因为 $1$ 是 $2^0$，$2$ 是 $2^1$，$4$ 是 $2^2$。

输入格式

第一行一个整数 $t$，表示数据组数，$1\le t\le 100$。

接下来 $t$ 行，每行一个整数 $n$，$1\le n\le 10^9$。

输出格式

对于每组数据，在一行中输出一个整数，表示答案。

2
4
1000000000

-4
499999998352516354