Bài tập

Một nhà thám hiểm muốn ghé thăm đủ \(N\) thành phố, được đánh số từ \(1\) đến \(N\), bằng đường hàng không. Anh ta được tự do chọn thành phố xuất phát, sau đó bay lần lượt qua các thành phố còn lại sao cho mỗi thành phố được ghé đúng một lần (không cần quay về điểm đầu).

Giá vé bay thẳng từ thành phố \(i\) đến thành phố \(j\) là \(c_{i,j}\) (giá vé chiều đi và chiều về có thể khác nhau). Hãy tìm tổng tiền vé nhỏ nhất của một hành trình như vậy.

Input

• Dòng đầu chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(N\) số nguyên \(c_{i,1}, c_{i,2}, \dots, c_{i,N}\).

Output

In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Constraints

• \(1 \le N \le 16\).
• \(c_{i,i} = 0\); với \(i \ne j\) thì \(1 \le c_{i,j} \le 10^9\).

Sample Input

4
0 3 1 5
2 0 4 1
6 2 0 3
1 7 2 0

Sample Output

3

Explanation

Hành trình \(2 \to 4 \to 1 \to 3\) có tổng chi phí \(1 + 1 + 1 = 3\).

Có \(30\) lớp tham dự một cuộc thi, mỗi lớp cử đúng \(N\) học sinh. Trước giờ thi, mọi thí sinh đều bắt tay từng người trong số những thí sinh còn lại (cùng lớp hay khác lớp đều bắt), và hai người chỉ bắt tay nhau đúng một lần. Tính tổng số cái bắt tay.

Input

Một số nguyên \(N\).

Output

Tổng số cái bắt tay.

Constraints

• \(1 \le N \le 35\)

Sample Input

2

Sample Output

1770

Explanation

Với \(N=2\) có \(60\) người, số cặp là \(60\cdot59/2=1770\).

Cho hai số nguyên dương \(A\) và \(B\). Hãy viết chương trình in ra giá trị \(A + B\).

Input

• Dòng đầu tiên chứa số nguyên \(A\).
• Dòng thứ hai chứa số nguyên \(B\).

Output

• Một số nguyên duy nhất là tổng \(A + B\).

Constraints

• \(1 \le A, B \le 10^9\)

Sample Input

15
27

Sample Output

42

Cho một dãy gồm \(n\) số nguyên dương. Hãy đếm xem trong dãy có bao nhiêu phần tử là số nguyên tố (các phần tử trùng nhau được đếm riêng).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \le n < 10^3)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 2 \cdot 10^9)\).

Output

• In ra một số nguyên duy nhất là số lượng phần tử của dãy là số nguyên tố.

Example

Input

10
1 2 2 4 5 6 7 9 11 13

Output

6

Note

Các số nguyên tố trong dãy là \(2, 2, 5, 7, 11, 13\).