Cho một số nguyên \(n\). Hãy tính tổng từ \(1\) đến \(n\), ngoại trừ những số là lũy thừa của \(2\) thì sử dụng phép trừ.

Ví dụ: với \(n=5\) thì tổng cần tìm là: \(−1−2+3−4+5=1\), vì \(1,2,4\) lần lượt là \(2^0\),\(2^1\),\(2^2\).

Bạn cần làm \(t\) bộ dữ liệu.

Input

• Dòng đầu tiên là số nguyên dương \(t\) là số lượng bộ dữ liệu.
• \(t\) dòng tiếp theo, mỗi dòng là 1 số nguyên \(N\).

Output

• Gồm \(t\) dòng , mỗi dòng là tổng cần tìm với \(n\) tương ứng.

Constraints

• \(1 \leq t \leq 100\)
• \(1 \leq N \leq 10^{9}\)

Example

2
5
536870912 

1
144115186196807682