Định nghĩa:

• Hàm \(f(n)\) = \(1|2 + 2|3 + ... (n-1)|n + n|(n+1)\). Trong đó | là phép toán \(Or\).

Yêu cầu: Tính hàm \(f(n)\), với \(n\) được nhập từ bàn phím.

Input

• Dòng đầu ghi \(q\) không quá \(100\) - số câu hỏi.
• \(q\) dòng tiếp theo, mỗi dòng ghi số nguyên dương \(n\) không quá \(10^6\).

Output

• Ứng với mỗi câu hỏi, in ra kết quả tương ứng.

Example

3
3
2
1

13
6
3