Contest Lì xì đầu năm cho bảng A

Trong quan niệm của Khang, một năm gọi là may mắn nếu nó chỉ có một chữ số khác 0.

Ví dụ: \(1\), \(10\) là năm may mắn. Biết năm nay là năm \(n\), hỏi Khang phải đợi bao năm nữa để đến năm may mắn.

Input

• Một số tự nhiên \(n\) \((1 \le n \le 10^{15})\).

Output

• In ra số năm Khang phải đợi để đến năm may mắn tiếp theo.

Example

4

1

201

99

Theo phiên âm Hán Việt số 8 là bát (đọc trại là phát), số 6 là lục (đọc trại là lộc). Và vì thế số 86 đọc trại là phát lộc.

Định nghĩa: số chính phương là bình phương của một số tự nhiên. Ví dụ: 9 là số chính phương vì \(9 = 3 \cdot 3\).

Yêu cầu: Cho số tự nhiên \(n\) \((1 \leq n \leq 10^{18})\). Đếm số lượng số \(m\) có giá trị từ 1 đến \(n\) sao cho:

• \(m\) là số chính phương
• \(m\) chia hết cho 8 hoặc \(m\) chia hết cho 6

Input

• Một dòng duy nhất chứa số tự nhiên \(n\) \((1 \leq n \leq 10^{18})\)

Output

• In ra số lượng số \(m\) thỏa mãn yêu cầu đề bài

Example

100

3

Khang rất thích hai chữ số 8 và 6 vì anh ấy quan niệm rằng chữ số 8 là Phát còn chữ số 6 là Lộc.

Nhân dịp đầu xuân Bính Ngọ 2026, Khang dành riêng cho Team HĐK 2026 một bài tập về Phát Tài Phát Lộc như sau:

Với số khởi đầu là 86 (Phát Lộc), với mỗi lần biến đổi theo qui tắc sau:

• Lấy số nhân cho 8 rồi cộng cho 6
• Sau đó lấy số mod cho \(m\) \((2 \leq m \leq 100000)\)

Input

• Dòng 1: số nguyên dương \(n\) \((1 \leq n \leq 10^{12})\)
• Dòng 2: số nguyên dương \(m\) \((2 \leq m \leq 100000)\)

Output

In ra trên 2 dòng:

• Dòng 1: số nhận được sau lần biến đổi thứ \(n\)
• Dòng 2: tổng các số đã biến đổi từ lần thứ 1 đến lần biến đổi thứ \(n\)

Example

3
88866

44470
50722

100
88666

46322
4055392

Định nghĩa:

• Giá trị của ngày được tính là \((\text{ngày} \cdot 2) + \text{tháng + hai chữ số cuối của năm}\). Ví dụ: ngày 1 tháng 2 năm 2026 thì giá trị của ngày là: \((1 \cdot 2) + 2 + 26 = 30\).
• Ngày may mắn là ngày có giá trị của ngày chia hết cho \(6\).

Cho một ngày tháng năm, hãy tính số lượng ngày may mắn từ ngày 1 tháng 1 năm 1 đến ngày tháng năm cho trước.

Lưu ý: Năm nhuận được tính theo lịch Gregory hiện tại:

• Năm nhuận là năm chia hết cho \(400\)
• Hoặc năm chia hết cho \(4\) nhưng không chia hết cho \(100\)
• Các năm nhuận thì tháng 2 có 29 ngày

Input

• Một dòng duy nhất chứa 3 số nguyên dương \(ngày\), \(tháng\), \(năm\)
• Dữ liệu đảm bảo là ngày tháng năm hợp lệ
• \(1 \leq năm \leq 10^{14}\)

Output

• In ra số lượng ngày may mắn tính từ ngày 1 tháng 1 năm 1 đến ngày tháng năm được cho

Example

31 12 100

6092

Định nghĩa: Số chẵn lẻ đan xen là số tự nhiên mà 2 chữ số liên tiếp trong số đó không cùng chẵn hoặc không cùng lẻ. Mặc định số một chữ số là số chẵn lẻ đan xen.

Cho số tự nhiên \(n\), hãy tìm số tự nhiên \(m\) lớn nhất không vượt quá \(n\) là số chẵn lẻ đan xen.

Input

• Một số tự nhiên \(n\) \((n \leq 10^{100})\)

Output

• In ra số \(m\) thỏa mãn đề bài

Example

11

10

Cho một xâu s chỉ chứa các kí tự tiếng Anh in thường từ 'a' đến 'z'. Độ dài xâu s không vượt quá \(10^5\).

Thực hiện mã hóa xâu s thành xâu t như sau:

• Ban đầu xâu t là rỗng
• Đưa một kí tự của xâu s vào cuối xâu t và thực hiện đảo xâu t. Nếu xâu t hiện tại có độ dài là chẵn thì đảo nửa trái xâu t và nửa phải xâu t (cắt nửa trái xâu t rồi đảo, cắt nửa phải xâu t rồi đảo, xong ghép 2 phần đảo thành xâu t mới). Các kí tự của xâu s đưa lần lượt vào xâu t như vậy.

Input

• Một dòng duy nhất chứa xâu t đã được mã hóa (độ dài không quá \(10^5\))
• Xâu t chỉ chứa các kí tự in thường từ 'a' đến 'z'

Output

• In ra một dòng duy nhất là xâu s ban đầu.

Example

akjshjdosjksjkoka

hkjjsodsjkokkasja