Trên một đường tròn ta chấm ngẫu nhiên ~x~ điểm, sau đó lần lượt nối các cặp hai điểm lại bằng các đoạn thẳng. Khi đó, hình tròn sẽ bị chia ra thành nhiều miền khác nhau.

Hỏi số lượng miền tối đa có thể thu được là bao nhiêu?

Input

• Dòng 1: số nguyên dương ~T~ (~1 \le T \le 1000~)
• Dòng 2: ~T~ số nguyên dương ~x_1, x_2, \cdots, x_n~

Output

In ra 1 dòng gồm ~T~ số nguyên dương ~y_i~ cách nhau bởi dấu cách, mỗi số nguyên dương ~y_i~ là số miền tối đa tạo trên hình tròn khi nối các cặp hai điểm trong ~x_i~ điểm ngẫu nhiên trên đường tròn.

Ví dụ

Sample Input

5
1 2 3 4 5

Sample Output

1 2 4 8 16

Giải thích

• ~x_i = 4 \implies y_i = 8~

Subtasks

• Subtask 1 (10%): ~a_i \le 5~
• Subtask 2 (25%): ~a_i \le 50~
• Subtask 3 (30%): ~a_i \le 500~
• Subtask 4 (35%): ~a_i \le 50000~