Bài tập

Cô giáo chủ nhiệm mang kẹo đến chia cho lớp có \(N\) học sinh đứng xếp hàng. Bạn đứng đầu hàng nhận \(1\) viên; mỗi bạn đứng sau luôn nhận nhiều hơn bạn ngay trước mình đúng \(3\) viên (tức là các bạn lần lượt nhận \(1, 4, 7, 10, \dots\) viên).

Hãy cho biết cô giáo cần chuẩn bị tối thiểu bao nhiêu viên kẹo để chia hết cho cả lớp.

Input

• Một số nguyên \(N\) duy nhất.

Output

• In ra một số nguyên là tổng số kẹo cần chuẩn bị.

Constraints

• \(0 \le N \le 45000\).

Sample Input 1

3

Sample Output 1

12

Sample Input 2

5

Sample Output 2

35

Explanation

Với \(N = 5\) các bạn nhận \(1, 4, 7, 10, 13\) viên, tổng là \(35\).

Hai anh em được cô chú tặng nhiều gói kẹo và muốn chia thành hai phần sao cho số kẹo ở hai phần chênh nhau ít nhất có thể. Các gói kẹo phải được giữ nguyên, không được bóc ra.

Có \(N\) gói kẹo, gói thứ \(i\) có \(A_i\) viên. Hãy chia toàn bộ các gói vào hai phần (một phần có thể rỗng) sao cho hiệu tuyệt đối giữa tổng số viên kẹo hai phần là nhỏ nhất, và in ra hiệu đó.

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng: dòng đầu chứa \(N\); dòng sau chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

Với mỗi bộ dữ liệu, in ra một dòng chứa hiệu tuyệt đối nhỏ nhất.

Constraints

• \(1 \le T \le 20\)
• \(1 \le N \le 100\)
• \(1 \le A_i \le 500\)

Sample Input

2
5
3 9 4 4 8
3
10 10 7

Sample Output

2
7

Explanation

Bộ 1: tổng số kẹo là \(28\), nếu chia đều mỗi bên phải là \(14\) nhưng không có tập gói nào có tổng \(14\). Chia \(\{9,4\}\) (\(13\)) và \(\{3,4,8\}\) (\(15\)) cho hiệu \(2\), đây là nhỏ nhất. Bộ 2: chia \(\{10,7\}\) (\(17\)) và \(\{10\}\) (\(10\)) cho hiệu \(7\), là nhỏ nhất.

Cho một dãy gồm \(N\) số nguyên dương. Hãy kiểm tra xem có thể chia toàn bộ các số của dãy thành hai nhóm (mỗi số thuộc đúng một nhóm) sao cho tổng các số ở hai nhóm bằng nhau hay không.

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng: dòng đầu chứa \(N\); dòng sau chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

Với mỗi bộ dữ liệu in ra YES nếu chia được, ngược lại in NO.

Constraints

• \(1 \le T \le 20\)
• \(1 \le N \le 100\)
• \(1 \le A_i \le 1000\)

Sample Input

3
5
2 3 7 4 6
4
2 2 2 9
1
8

Sample Output

YES
NO
NO

Explanation

Bộ 1: tổng \(22\), chia \(\{2,3,6\}\) và \(\{7,4\}\) đều được \(11\) nên YES. Bộ 2: tổng \(15\) là số lẻ nên NO. Bộ 3: chỉ có một số nên không thể chia đều, NO.

Sắn có một dãy \(N\) món đồ chơi xếp trong tủ theo thứ tự mua, món thứ \(i\) có giá \(v_i\). Sau khi thua cược, Sắn phải chia đồ chơi cho Mì theo cách sau: Sắn chọn trước một số nguyên \(x \in \{1, 2, 3\}\), sau đó hai bạn lần lượt lấy đồ chơi từ đầu dãy: Sắn lấy \(x\) món đầu tiên, Mì lấy \(x\) món tiếp theo, rồi lại đến Sắn \(x\) món, ... cho đến khi hết đồ (nếu lượt cuối còn ít hơn \(x\) món thì người đó lấy hết số còn lại).

Sắn muốn phần của mình có tổng giá trị lớn nhất có thể. Hãy chọn \(x\) tối ưu và in ra tổng giá trị đó.

Input

• Dòng đầu chứa số bộ test \(T\).
• Mỗi bộ test gồm hai dòng: dòng thứ nhất là \(N\), dòng thứ hai gồm \(N\) số nguyên \(v_1, \dots, v_N\).

Output

Với mỗi bộ test in một dòng: tổng giá trị lớn nhất Sắn có thể nhận.

Constraints

• \(1 \le T \le 10\)
• \(1 \le N \le 10^5\)
• \(1 \le v_i \le 10^9\)

Sample Input

2
5
9 2 4 6 1
7
3 8 8 1 5 2 7

Sample Output

15
26

Explanation

Bộ test 1: với \(x = 3\) Sắn lấy \(9, 2, 4\) được \(15\) (Mì lấy \(6, 1\)); các giá trị \(x = 1, 2\) chỉ cho \(14\) và \(12\). Bộ test 2: với \(x = 3\) Sắn lấy \(3, 8, 8\) và \(7\), tổng \(26\).