Nhớ em

Trong giờ học Vật lý, một thành viên của CLB CHTCoder đang lơ đãng nhớ về crush thì bị thầy phát hiện.

Để không bị trừ điểm hoặc ghi vào sổ đầu bài, thầy đã giao cho hai bạn một thử thách:
Cho một bảng kích thước \(n \times n\), trong đó các số được điền theo thứ tự tăng dần từ trái sang phải và từ trên xuống dưới, bắt đầu từ \(1\) cho tới \(n \times n\).

Yêu cầu của thầy rất đơn giản: Tính tổng các phần tử nằm trên đường chéo chính của bảng.

Input

Đọc từ file NHOEM.INP:

• Số nguyên dương \(t\) (\(1 \le t \le 10^{6}\)) --- số câu hỏi.
• Mỗi dòng tiếp theo chứa một số nguyên dương \(n\) (\(1 \le n \le 10^{6}\)).

Output

Ghi ra file NHOEM.OUT:

• Gồm \(t\) dòng, mỗi dòng là tổng đường chéo chính tương ứng.

Example

2
3
6

15
111

Scoring

• Subtask 1 (70%): \(1 \le t, n \le 10^{3}\).
• Subtask 2 (30%): Không có ràng buộc thêm.