Một lục giác đều với độ dài cạnh là số nguyên dương có thể được ghép bằng một số tam giác đều có độ dài cạnh bằng ~1~. Ví dụ dưới đây là hai hình lục giác đều được ghép bằng các tam giác đều cạnh ~1~.

Yêu cầu

Hỏi rằng số tam giác đều tối thiểu là bao nhiêu để ghép được ~n~ hình lục giác đều với độ dài các cạnh lần lượt là ~1, 2, ..., n~?

Dữ liệu đầu vào

Gồm ~T + 1~ dòng:

• Dòng đầu chứa số nguyên dương ~T~ ~(T \le 10^5)~ là số lượng bộ dữ liệu.
• Tiếp theo là ~T~ dòng, mỗi dòng chứa một số nguyên dương ~n~ ~(1 \le n \le 10^6)~ mô tả một bộ dữ liệu (các bộ dữ liệu được đánh số ~1, 2, ..., T~).

Dữ liệu đầu ra

Gồm ~T~ dòng, dòng thứ ~i~ ~(i = 1, 2, ..., T)~ chứa một số nguyên là kết quả của bộ dữ liệu thứ ~i~.

Ràng buộc dữ liệu

• 60% số test kiểm tra ứng với 40% số điểm của bài có ~T \le 10, n \le 1000~.
• 40% số test còn lại ứng với 40% số điểm của bài có ~10 < T \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

3
1
2
3

OUTPUT

6
30
84

Cho dãy số nguyên ~a_1, a_2, ..., a_n~. Chia dãy này thành ~2~ phần:

• Phần thứ nhất gồm các số ~a_1, a_2, ..., a_k~ ~(1 \le k < n )~.
• Phần thứ hai gồm các số còn lại.

Yêu cầu

Gọi ~T_1~ và ~T_2~ lần lượt là tổng các số của phần thứ nhất và phần thứ hai. Tìm giá trị nhỏ nhất của ~|T_1 - T_2|~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(2 \le n \le 10^6)~.
• Dòng thứ hai chứa các số nguyên ~a_1, a_2, ..., a_n~ ~(|a_i| \le 10^9\ \forall\ i = 1, 2, ..., n)~ cách nhau bằng dấu trống.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là giá trị nhỏ nhất của ~|T_1 - T_2|~.

Ràng buộc dữ liệu

• 75% số test kiểm tra ứng với 75% số điểm của bài có ~n \le 5000~.
• 25% số test còn lại ứng với 25% số điểm của bài có ~n > 5000~.

Ví dụ

Ví dụ 1

INPUT

5
1 2 3 4 5

OUTPUT

3

An có ~n~ đoạn thẳng. Cậu ta nhận thấy rằng một số đoạn thẳng có cùng chiều dài nên có thể xếp thành những hình vuông.

Yêu cầu

Hỏi rằng số hình vuông nhiều nhất An có thể xếp được là bao nhiêu?

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^{18})~ cách nhau bằng dấu trống.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số lượng hình vuông lớn nhất An có thể xếp được.

Ràng buộc dữ liệu

• 30% số test kiểm tra ứng với 30% số điểm của bài có ~n \le 2000, a_i \le 10^6~.
• 30% số test tiếp theo ứng với 30% số điểm của bài có ~n > 2000, a_i \le 10^6~.
• 40% số test còn lại ứng với 40% số điểm của bài có ~n > 2000, a_i \le 10^{18}~.

Ví dụ

Ví dụ 1

INPUT

9
2 2 2 9 2 2 2 2 2

OUTPUT

2

Cho dãy số nguyên ~a_1, a_2, ..., a_n~.

Yêu cầu

Hãy tính giá trị lớn nhất của biểu thức: ~a_i \times a_j \times a_k~ với ~1 \le i < j < k \le n~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu chứa số nguyên dương ~n~ ~(3 \le n \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(|a_i| \le 10^6\ \forall\ i = 1, 2, ..., n)~ cách nhau bằng dấu trống.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả tìm được.

Ràng buộc dữ liệu

• 40% số test kiểm tra ứng với 40% số điểm của bài có ~n \le 100~.
• 60% số test còn lại ứng với 60% số điểm của bài có ~n > 100~.

Ví dụ

Ví dụ 1

INPUT

6
5 2 10 1 3 2

OUTPUT

150

Cho dãy số nguyên dương ~a_1, a_2, ..., a_n~.

Yêu cầu

Hãy đếm số cặp ~(i, j)~ với ~1 \le i < j \le n~ thoả mãn tính chất: Số ~a_i \times a_j~ là số chính phương (số nguyên dương ~x~ được gọi là số chính phương nếu tồn tại số nguyên ~y~ sao cho ~x = y^2~).

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \le 10^6)~.
• Dòng thứ hai chứa các số nguyên ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^6\ \forall \ i = 1, 2, ..., n)~ cách nhau bằng dấu trống.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số cặp tìm được

Ràng buộc dữ liệu

• 40% số test ứng với 40% số điểm của bài có ~n \le 2000~.
• 40% số test tiếp theo ứng với 40% số điểm của bài có ~n > 2000, a_i \le 10^4~.
• 20% số test còn lại ứng với 20% số điểm của bài có ~n > 2000, a_i \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

5
2 8 3 75 27

OUTPUT

4