Alan Turing là một nhà toán học, logic học và nhà tiên phong khoa học máy tính người Anh. Ông được xem là cha đẻ của trí tuệ nhân tạo và điện toán hiện đại. Trong Thế chiến II, Alan Turing đóng vai trò quan trọng trong việc giải mã máy Enigma của Đức Quốc xã.

Cho biết năm sinh của Alan Turing là một số chia hết cho \(8\). Nhập ba số nguyên \(y, a, b\) \((1930 \le y \le 1954;\;0 \le a, b \le 10^9)\), gọi \(t\) là tuổi của Alan Turing ở năm \(y\), hãy tính giá trị \(t \times a + b.\)

Input

• Một dòng chứa ba số nguyên \(y, a, b\) \((1930 \le y \le 1954;\;0 \le a, b \le 10^9)\).

Output

• Một dòng chứa một số là giá trị \(t \times a + b\).

Example

1930 0 10

10

Alice có dãy số nguyên \((a_1, a_2, \dots, a_n)\) và số nguyên dương \(k\). Alice muốn chọn ra \(k\) chỉ số \(1 \le i_1 < i_2 < \dots < i_k \le n\) để giá trị \(S = 1 \times a_{i_1} + 2 \times a_{i_2} + \dots + k \times a_{i_k}\) đạt giá trị lớn nhất.

Ví dụ, với dãy \((-3,1,-3,-4,-5)\) và \(k = 2\), nếu chọn \(i_1 = 1, i_2 = 2\) thì \(S = -3 + 2 = -1\), còn nếu chọn \(i_1 = 2, i_2 = 3\) thì \(S = 1 + (-6) = -5\). Trong tất cả các cách chọn \(1 \le i_1 < i_2 \le 5\) thì \(S = -1\) đạt giá trị lớn nhất.

Yêu cầu: Giúp Alice tính giá trị \(S\) lớn nhất đạt được.

Input

• Dòng đầu chứa hai số nguyên dương \(n, k\) \((1 \le k \le 5 \le n)\);
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((|a_i| \le 10^9)\).

Output

• Ghi một dòng chứa một số nguyên \(S\) lớn nhất đạt được.

Subtasks

• Subtask 1 (30%): \(k = 1; n \le 300\)
• Subtask 2 (20%): \(k = 2; n \le 300\)
• Subtask 3 (30%): \(k = 3; n \le 10^5\)
• Subtask 4 (20%): \(n \le 10^5\).

Example

5 2
-3 1 -3 -4 -5

-1

Cho hai số nguyên dương \(1 \le L \le R \le 10^9\) và số nguyên dương \(k\) \((k \le 10^9)\).
Tìm số \(X\) có thứ tự từ điển nhỏ nhất thỏa mãn \(L \le X \le R\) và chia hết cho \(k\) nhưng tổng các chữ số của \(X\) là một số nguyên tố.

Chú ý: so sánh hai số theo thứ tự từ điển nghĩa là so sánh chúng như hai chuỗi ký tự (string).

Input

• Gồm nhiều dòng, mỗi dòng chứa ba số nguyên \(L, R, k\).

Output

• Gồm nhiều dòng, mỗi dòng chứa số \(X\) tìm được tương ứng với dữ liệu vào; nếu không tồn tại thì ghi \(-1\).

Subtasks

• Subtask 1 (30%): \(R, k \le 10^4\)
• Subtask 2 (30%): \(k \le 10^4\)
• Subtask 3 (40%): Không có ràng buộc nào thêm

Example

4 7 5
11 19 10
4 111 10

5
-1
110

Cho \(n\) điểm trên mặt phẳng, không có ba điểm nào thẳng hàng, các điểm được đánh số từ \(1\) đến \(n\). Người ta nối tất cả các cặp điểm \((i, j)\) bằng sợi dây màu xanh hoặc màu vàng theo nguyên tắc: nếu \(i + j\) là số nguyên tố thì nối điểm \(i\) với điểm \(j\) bằng sợi dây màu xanh, ngược lại nối bằng sợi dây màu vàng. Hỏi có bao nhiêu tam giác sao cho cả ba đỉnh đều được nối với nhau bằng sợi dây cùng màu.

Input

• Dòng đầu tiên ghi số nguyên dương \(T\) \((T \le 10)\) là số lượng bộ dữ liệu.
• Tiếp đến là \(T\) dòng, mỗi dòng chứa một số nguyên \(n\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa một số nguyên là số tam giác đếm được tương ứng với bộ dữ liệu vào.

Subtasks

• Subtask 1 (30%): \(n \le 100\).
• Subtask 2 (30%): \(n \le 1000\).
• Subtask 3 (40%): \(n \le 10^6\).

Example

2
3
5

0
1