Bài tập

Ông Geppetto có \(N\) thanh gỗ, thanh thứ \(i\) dài \(A_i\). Để chế tác chiếc mũi cho Pinocchio, ông lặp lại quy trình sau cho tới khi chỉ còn đúng một thanh:

1. Chọn ra hai thanh ngắn nhất hiện có, gọi độ dài của chúng là \(p \le q\) (nếu có nhiều thanh cùng độ dài thì chọn tuỳ ý, kết quả không phụ thuộc cách chọn).
2. Nếu \(p = q\) thì bỏ đi một trong hai thanh.
3. Nếu \(p < q\) thì cắt bớt thanh dài \(q\) đi một đoạn dài \(p\), tức là thanh đó còn lại độ dài \(q - p\).

Khi chỉ còn một thanh, thanh đó là chiếc mũi. Hãy tính độ dài của nó.

Input

• Dòng 1: số nguyên dương \(N\).
• Dòng 2: \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\).

Output

• In ra một số nguyên là độ dài thanh gỗ cuối cùng.

Constraints

• \(1 \le N \le 100000\).
• \(1 \le A_i \le 10^9\).

Sample Input

4
12 18 30 8

Sample Output

2

Explanation

Quy trình giữ nguyên ước chung lớn nhất của cả nhóm nên kết quả là \(\gcd(12, 18, 30, 8) = 2\).

Với mỗi số nguyên \(x \ge 2\), ký hiệu \(f(x)\) là ước lớn nhất của \(x\) nhỏ hơn \(x\) (ví dụ \(f(12) = 6\), \(f(7) = 1\), \(f(9) = 3\)).

Cho số nguyên \(N\). Ta muốn tách \(N\) thành tổng của một hay nhiều số nguyên, mỗi số không nhỏ hơn 2:

Chi phí của một cách tách là \(f(k_1) + f(k_2) + \dots + f(k_m)\). Cách tách chỉ gồm một số (\(m = 1\), \(k_1 = N\)) cũng hợp lệ.

Hãy tính chi phí nhỏ nhất có thể đạt được.

Input

Một dòng duy nhất chứa số nguyên \(N\).

Output

In ra chi phí nhỏ nhất.

Constraints

• \(2 \le N < 10^9\)

Sample Input

27

Sample Output

3

Explanation

Có thể tách \(27 = 7 + 7 + 13\), cả ba số đều là số nguyên tố nên mỗi số có chi phí \(1\), tổng chi phí là \(3\). Không có cách tách nào cho tổng chi phí nhỏ hơn.

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.