F. OR Pairs
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$.

Your task is to find the number of pairs $$$a$$$ and $$$b$$$ that:

  • $$$0 \le a \le b$$$;
  • $$$a$$$ | $$$b \le n$$$.

| means Bitwise OR Operation.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases. The description of the test cases follows.

The each test case contains a single integer $$$n$$$ $$$(0 \le n \le 10^{9})$$$.

Output

For each test case, output a single integer — the number of pairs.

Example
Input
5
0
1
6
7
8
Output
1
3
22
36
38