Max y la Suma

En este problema debes calcular la suma de todos los enteros de 1 a n, pero para ello debes remplazar por el mismo número negativo aquellos que puedan ser calculados como una potencia de 2.

Por ejemplo, para n = 4 la suma sería igual a 1+2+3+4 pero 1,2,4 pueden ser calculados como potencia de 2 (2⁰ , 2¹ y 2² respectivamente) entonces la suma quedaría igual a  -1-2+3-4 = -4.

Calcule la respuesta para los valores t de n.

Input

La primera línea de la entrada contiene un entero único t (1 ≤  t  ≤ 100) - el número de valores de n a procesar.

 Cada una de las próximas líneas t contiene un entero único n (1 ≤  n  ≤ 10⁹).

Output

Imprimir la suma solicitada para cada uno de t enteros n dados en la entrada (uno por línea).

Example

Input:
2 
4 
10
Output:
-4 
 25
 
Nota
 
La respuesta para el primer caso se explicó en el ejemplo del enunciado
 
Para el segundo caso, 1, 2, 4 y 8 pueden ser calculados como potencia de 2 (20, 21, 22 y 23 respectivamente) entonces la suma quedaría igual a:
  -1-2+3-4+5+6+7-8+9+10 = 25.