B. A Cool Pair Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

For the integer $$$n$$$, a pair $$$(a,b)$$$ is considered cool only if:

  • $$$1 \le a \lt b \le n$$$;
  • $$$a$$$ $$$\&$$$ $$$b$$$ $$$=$$$ $$$0$$$, where $$$\&$$$ denotes the bitwise AND operation.

For a given integer $$$n$$$, find the maximum value of $$$a \cdot b$$$ among all cool pairs $$$(a, b)$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), the number of test cases.

For each test case, the only line contains a single integer $$$n$$$$$$(2 \le n \le 10^9)$$$.

Output

For each test case, print the maximum value of $$$a \cdot b$$$ for all cool pairs $$$(a, b)$$$.

Example
Input
4
2
9
996
1000000000
Output
2
56
261632
288230375614840832