Bài tập

Cho ba số nguyên dương \(A\), \(B\) và \(N\). Hãy tính ước chung lớn nhất của hai số \(A^N\) (tức là \(A\) nhân với chính nó \(N\) lần) và \(B\), ký hiệu \(\gcd(A^N, B)\).

Lưu ý rằng \(A^N\) có thể lớn hơn rất nhiều so với phạm vi biểu diễn của các kiểu số nguyên thông thường.

Input

Một dòng duy nhất chứa ba số nguyên \(A\), \(B\), \(N\) cách nhau bởi dấu cách.

Output

In ra một số nguyên duy nhất là giá trị \(\gcd(A^N, B)\).

Constraints

• \(1 \le A, B \le 10^9\)
• \(1 \le N \le 10^{15}\)

Sample Input 1

12 90 1

Sample Output 1

6

Sample Input 2

6 72 2

Sample Output 2

36

Explanation

• Ví dụ 1: \(12^1 = 12\) và \(\gcd(12, 90) = 6\).
• Ví dụ 2: \(6^2 = 36\) và \(\gcd(36, 72) = 36\).

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