Cho sân trường Newton có dạng hình chữ nhật với chiều dài ~A~ mét và chiều rộng ~B~ mét.

Để chuẩn bị cho ngày hội thể thao, nhà trường muốn treo dây cờ trang trí dọc theo toàn bộ mép sân. Mỗi dây cờ có cùng độ dài là ~L~ mét và các dây cờ sẽ được nối tiếp liên tục với nhau.

Yêu cầu: Hãy tính số dây cờ ít nhất mà nhà trường cần mua để treo đủ quanh sân.

Dữ liệu nhập vào từ bàn phím

• Gồm ba số tự nhiên ~A~, ~B~ và ~L~ (~1 \le A, B, L \le 100~). Mỗi số trên một dòng.

Kết quả ghi ra màn hình

• In ra một số tự nhiên là số dây cờ ít nhất cần mua.

Ví dụ

Input

20 
15 
8

Output

9

Giải thích: Chu vi sân là ~2 \times (20 + 15) = 70~ mét. Mỗi dây dài ~8~ mét nên cần ~9~ dây mới treo đủ quanh sân.

Cho một dãy gồm năm số tự nhiên tăng dần. Biết rằng dãy số này ban đầu là một cấp số cộng gồm năm phần tử, nhưng trong quá trình ghi chép đã bị bỏ sót mất một phần tử ở giữa (chắc chắn phần tử bị thiếu không phải là phần tử đầu tiên và cũng không phải là phần tử cuối cùng).

(Nhắc lại kiến thức: Cấp số cộng là một dãy số thỏa mãn điều kiện kể từ số hạng thứ hai, mỗi số hạng đều bằng số hạng đứng ngay trước nó cộng với một số không đổi gọi là công sai).

Yêu cầu: Dựa vào bốn số tự nhiên còn lại, hãy tìm và khôi phục lại giá trị của số bị viết thiếu.

Dữ liệu nhập vào từ bàn phím

• Gồm bốn số tự nhiên ~a, b, c, d~ theo đúng thứ tự xuất hiện của dãy hiện tại. Mỗi số trên một dòng.

Các số có giá trị không quá ~1000~.

Kết quả ghi ra màn hình

• In ra một số tự nhiên duy nhất là giá trị của phần tử bị viết thiếu.

Ví dụ

Ví dụ 1:

Input

2 
4 
8 
10

Output

6

Giải thích: Dãy ban đầu là cấp số cộng có công sai là 2. Dãy hoàn chỉnh gồm 5 phần tử là: 2, 4, 6, 8, 10. Số bị thiếu ở giữa là 6.

Ví dụ 2:

Input

10 
20 
30 
50

Output

40

Giải thích: Dãy ban đầu là cấp số cộng có công sai là 10. Dãy hoàn chỉnh gồm 5 phần tử là 10, 20, 30, 40, 50. Số bị thiếu ở giứa là 40.

Ta có một dãy các bảng hình vuông được tạo và tô màu theo quy luật mở rộng từ trong ra ngoài như sau:

Yêu cầu: Cho số tự nhiên ~N~, hãy tính tổng số ô vuông được tô màu ở hình thứ ~N~.

Dữ liệu nhập vào từ bàn phím

• Gồm một dòng duy nhất chứa số tự nhiên ~N~.

Kết quả ghi ra màn hình

• In ra một số tự nhiên là tổng số lượng ô vuông được tô màu ở hình thứ ~N~.

Ví dụ

Input

4

Output

24

Giải thích: Tổng số ô được tô màu = (số ô của viền tô màu ngoài cùng) + (số ô của khối ~2 \times 2~ ở giữa) = ~(6 \times 6 - 4 \times 4) + 4 = 20 + 4 = 24~ ô.

Ràng buộc:

• Có 20% số test ứng với 20% số điểm: ~N \le 10~.
• Có 40% số test ứng với 40% số điểm: ~N \le 1000~.
• 40% số test còn lại ứng với 40% số điểm: ~N \le 10^7~.

Cho số nguyên dương ~N~.

Yêu cầu: Hãy đếm xem có bao nhiêu bộ số nguyên ~(a, b)~ thỏa mãn đồng thời các điều kiện sau:

• ~1 \le a, b \le N~.
• Tích ~a \times b~ chia hết cho ~9~.
• Hai bộ ~(a, b)~ và ~(b, a)~ được tính là khác nhau nếu ~a \neq b~.

Dữ liệu nhập vào từ bàn phím

• Gồm một số nguyên dương ~N~ (~1 \le N \le 10^7~).

Kết quả ghi ra màn hình

• Gồm một số nguyên là kết quả của bài toán. Vì kết quả có thể rất lớn nên in ra phần dư của kết quả khi chia cho 2026.

Ví dụ

Input

6

Output

4

Giải thích: Có ~4~ cặp ~(a, b)~ thỏa mãn tích ~a \times b~ chia hết cho ~9~ là: ~(3, 3), (3, 6), (6, 3), (6, 6)~.

Ràng buộc:

• Có 30% số test ứng với 30% số điểm: ~N \le 10^2~;
• 30% số test ứng với 30% số điểm: ~N \le 10^4~;
• 40% số test còn lại ứng với 40% số điểm không có ràng buộc gì thêm.

Xét một danh sách các số tự nhiên đặc biệt được lựa chọn dựa trên hai tính chất sau:

1. Thuộc nhóm số đối xứng: Nghĩa là giá trị của số đó không thay đổi khi bạn đọc từ trái sang phải hay từ phải sang trái. Ví dụ: ~1~, ~7~, ~121~, ~343~, ~90809~ là những số đối xứng hợp lệ. Ngược lại, ~12~, ~123~ không phải là số đối xứng.
2. Không có hai chữ số liền kề giống nhau: Các chữ số nằm sát cạnh nhau bắt buộc phải khác biệt. Chẳng hạn, các số ~121~ hay ~343~ là hợp lệ. Tuy nhiên, các số như ~11~, ~1001~, ~1221~ hay ~4554~ sẽ bị loại bỏ vì chứa các cặp chữ số giống hệt nhau đứng liền kề (như 11, 00, 22, 55).

Tập hợp tất cả các số tự nhiên thỏa mãn đồng thời cả hai tính chất trên và sắp xếp chúng theo thứ tự từ bé đến lớn, ta sẽ thu được một dãy số có dạng: ~1, 2, 3, 4, 5, 6, 7, 8, 9, 101, 121, 131, 141, 151, ...~

Yêu cầu: Cho trước một số tự nhiên ~N~, hãy xác định và in ra giá trị của số hạng đứng ở vị trí thứ ~N~ trong dãy số vừa được tạo ra.

Dữ liệu nhập vào từ bàn phím

• Gồm một dòng duy nhất chứa số tự nhiên ~N~.

Kết quả ghi ra màn hình

• In ra một số tự nhiên duy nhất là giá trị của số hạng thứ ~N~ trong dãy.

Ví dụ

Ví dụ 1:

Input

1

Output

1

Ví dụ 2:

Input

10

Output

101

Giải thích ví dụ 2: Các số hạng hợp lệ đầu tiên của dãy lần lượt là ~1, 2, 3, 4, 5, 6, 7, 8, 9, 101...~ Do đó, phần tử nằm ở vị trí thứ ~10~ chính là số ~101~.

Ràng buộc:

• Có 50% số test ứng với 50% số điểm: ~1 \le N \le 50~.
• Có 30% số test ứng với 30% số điểm: ~1 \le N \le 1000~.
• 20% số test còn lại ứng với 20% số điểm: ~1 \le N \le 10^5~.