Đến với chương đầu tiên, tất nhiên, chúng ta ban đầu ai cũng cần phải làm quen để có thể áp dụng các chương sau. Vì vậy, với chương này, D. sẽ dạy cho bạn cách tặng quà làm quen MỘT CÁCH ẤN TƯỢNG NHẤT.

Bạn sẽ tặng quà làm quen là một hoán vị $p$ độ dài $n$. Bạn hãy tìm hoán vị đó sao cho:

đạt giá trị lớn nhất.

Dù là phần đầu tiên nhưng cũng rất quan trọng nên bạn hãy vượt qua để tiếp tục tới với những chương tiếp theo nhé (cũng vì nó quan trọng nên chúng tôi đưa ra $t$ câu hỏi).

Lưu ý: quà tặng chỉ mang tính chất tham khảo, vui lòng không làm theo dưới mọi hình thức.

Input

• Dòng đầu tiên chứa số nguyên $t$ - số lượng câu hỏi ($t \leq 10$)
• $t$ dòng tiếp theo mỗi dòng chứa một số nguyên dương $n$. ($1\leq n \leq 10^{9}$)

Output

• Gồm $t$ dòng với mỗi dòng in ra giá trị $S$ thoả mãn đề bài tương ứng với $n$ của câu hỏi đó.

Subtasks

• Subtask 1: Đảm bảo $n\leq 10$. (20 điểm)
• Subtask 2: Đảm bảo $n\leq 10^6$. (40 điểm)
• Subtask 3: Không có ràng buộc gì thêm. (40 điểm)

Example

1
4

8