Kaosar and Count ORz

Input

The first line of each test case contains single integer $t$ (1 \le t \le 10^4) — the number of test cases.

The only line of each test case contains single integer $n$ (1 \le n \le 10^9) — the integer of the problem.

Output

For each test case , single integer — the answer to the problem.

Examples

Note

In the second test case , all such pairs are (2,4),(2,6),(4,2),(4,6)(6,2),(6,4)(6,6).

Scoring

1. Subtask $1$ ($20$ points) : (1 \le \sum n \le 1000)

2. Subtask $2$ ($30$ points) : (1 \le \sum n \le 10^6)

3. Subtask $3$ ($100$ points) : No additional constraints