Thầy giáo chủ nhiệm đội tuyển của bạn có một bài toán hơi lạ về hoán vị và nhờ bạn giải giúp.

Gọi chi phí của một hoán vị ~p~ có độ dài ~n~ là giá trị của biểu thức:

~(p1 \times 1 + p2 \times 2 + \dots + p_n \times n)

• \max(p_j \times j)~ với ~1 \le j \le n~.

Nói cách khác:

• Ta tính tổng ~S = \sum (p_i \times i)~.

• Tính ~M = \max(p_i \times i)~.

• Chi phí của hoán vị là ~S - M~.

Yêu cầu: Hãy tìm giá trị lớn nhất có thể của chi phí trong tất cả các hoán vị độ dài ~n~.

Hoán vị độ dài ~n~ là một mảng gồm ~n~ số nguyên phân biệt từ ~1~ đến ~n~ theo một thứ tự bất kỳ.

Ví dụ:

• ~[2, 3, 1, 5, 4]~ là một hoán vị.

• ~[1, 2, 2]~ không phải hoán vị vì số ~2~ xuất hiện hai lần.

• ~[1, 3, 4]~ không phải hoán vị độ dài ~3~ vì có số ~4~.

Input

• Dòng đầu chứa số nguyên ~t~ ~(1 \le t \le 30)~ - số bộ test.

• Mỗi test gồm đúng một dòng chứa số nguyên ~n~ ~(2 \le n \le 250)~ - độ dài của hoán vị.

Bảo đảm tổng các giá trị ~n~ trên tất cả các test không vượt quá ~500~.

Output

Với mỗi test, in ra một số nguyên - chi phí lớn nhất có thể của một hoán vị độ dài ~n~.

Scoring

Sample Input 1

5
2
4
3
10
20

Sample Output 1

2
17
7
303
2529

Notes

• Với ~n = 2~, một hoán vị tối ưu là ~[2, 1]~.

  Chi phí ~= 2 \cdot 1 + 1 \cdot 2 - \max(2 \cdot 1, 1 \cdot 2) = 2 + 2 - 2 = 2~.

• Với ~n = 4~, một hoán vị tối ưu là ~[1, 2, 4, 3]~.

  Chi phí ~= 1 \cdot 1 + 2 \cdot 2 + 4 \cdot 3 + 3 \cdot 4

  • 4 \cdot 3 = 17~.