Nam là một học sinh rất thông minh và có niềm đam mê với môn Tin học. Năm học này, Nam được cô giáo chọn vào đội tuyển luyện thi Tin học trẻ cấp thành phố. Nhận thấy được niềm đam mê và sự phấn khởi của Nam khi được chọn vào đội tuyển, bố Nam mua tặng cho Nam một chiếc máy tính xách tay để cho Nam có thể thuận lợi hơn trong việc ôn luyện thi.

Nam rất vui mừng khi nhận được món quà mà bố đã tặng. Nhớ đến bài học về bảo vệ thông tin trên máy tính mà cô giáo đã dạy, Nam đã tiến hành tạo mật khẩu cho máy tính của mình. Mật khẩu Nam tạo theo quy tắc như sau:

● Phần đầu của mật khẩu gồm chữ cái viết hoa đầu tiên và chữ cái viết thường cuối cùng của tên "Nam", tiếp theo là một ký tự đặc biệt @.

● Phần sau của mật khẩu là số nguyên dương nhỏ nhất vừa chia hết cho tổng ngày, tháng, năm sinh của bố và vừa chia hết cho tổng ngày, tháng, năm sinh của mẹ.

Yêu cầu: Hãy xác định mật khẩu mà Nam đã tạo.

Dữ liệu vào: Đọc từ tệp văn bản MATKHAU.INP gồm:

● Dòng thứ nhất ghi ba số nguyên dương d1, m1, y1 là ngày, tháng, năm sinh của bố Nam (1 ≤ d1 ≤ 31, 1 ≤ m1 ≤ 12, 0 < y1 < 10^4).

● Dòng thứ hai ghi ba số nguyên dương d2, m2, y2 là ngày, tháng, năm sinh của mẹ Nam (1 ≤ d2 ≤ 31, 1 ≤ m2 ≤ 12, 0 < y2 < 10^4).

Dữ liệu ra: Ghi ra tệp văn bản MATKHAU.OUT một dòng duy nhất là mật khẩu của Nam.

Ví dụ:

Input:

25 3 1983

3 9 1986

Output:

Nm@4017978

*Giải thích: *

Tổng ngày sinh của bố: 25 + 3 + 1983 = 2011.

Tổng ngày sinh của mẹ: 3 + 9 + 1986 = 1998.

Số nhỏ nhất vừa chia hết cho 2011 và 1998 là: 4017978.

⇒ Mật khẩu cần tìm là: Nm@4017978

Bạn đang quản lý một kho cây cảnh nhập từ nhiều nguồn khác nhau. Ban đầu kho hoàn toàn trống, mỗi ngày bạn nhận được một yêu cầu xử lý, có thể là nhập thêm cây hoặc dọn kho theo tiêu chí chiều cao. Cụ thể có q yêu cầu, mỗi yêu cầu thuộc một trong hai loại:

● 1 h: Nhập vào kho một cây cảnh có chiều cao h.

● 2 h: Do cần tối ưu không gian, bạn sẽ loại bỏ tất cả các cây có chiều cao không vượt quá h.

Yêu cầu: Sau mỗi yêu cầu trong số q yêu cầu, bạn cần báo cáo lại số lượng cây hiện còn trong kho.

Dữ liệu vào: Đọc từ tệp CAYCANH.INP có cấu trúc như sau:

● Dòng đầu tiên chứa số nguyên q (1 ≤ q ≤ 3·10^5) là số lượng yêu cầu.

● q dòng tiếp theo, mỗi dòng là một yêu cầu có dạng 1 h hoặc 2 h (1 ≤ h ≤ 10^9).

Dữ liệu ra: Ghi ra tệp CAYCANH.OUT gồm q dòng. Dòng thứ i là số lượng cây còn lại sau khi xử lý yêu cầu thứ i.

Ví dụ:

Input:

5 1 5 1 7 1 8 2 7

Output:

1 2 3 1 2

Giải thích:

Nhập cây cao 5 → kho có 1 cây.

Nhập cây cao 7 → kho có 2 cây.

Nhập cây cao 8 → kho có 3 cây.

Dọn các cây ≤ 7 (loại bỏ cây 5 và 7) → kho còn 1 cây.

Một số nguyên dương được gọi là Số đặc biệt nếu số lượng các ước số của nó là một số nguyên tố.

Ví dụ:

● Số 4 có các ước là {1, 2, 4}. Số lượng ước là 3. Vì 3 là số nguyên tố nên 4 là số đặc biệt.

● Số 6 có các ước là {1, 2, 3, 6}. Số lượng ước là 4. Vì 4 không phải là số nguyên tố nên 6 không phải là số đặc biệt.

Nam được cô giáo giao cho một danh sách các câu hỏi, mỗi câu hỏi yêu cầu đếm xem trong đoạn từ [L, R] có bao nhiêu số đặc biệt. Vì danh sách rất dài nên Nam phải viết một chương trình để giải quyết nhanh chóng.

Yêu cầu: Cho Q câu hỏi, mỗi câu hỏi gồm hai số nguyên L và R. Hãy đếm số lượng số đặc biệt trong đoạn [L, R].

Dữ liệu vào: Đọc từ tệp văn bản SODB.INP gồm:

● Dòng đầu tiên chứa số nguyên Q (1 ≤ Q ≤ 10^5) là số lượng câu hỏi.

● Q dòng tiếp theo, mỗi dòng chứa hai số nguyên dương L và R (1 ≤ L ≤ R ≤ 10^6).

Dữ liệu ra: Ghi ra tệp văn bản SODB.OUT gồm Q dòng, mỗi dòng là đáp án cho câu hỏi tương ứng.

Ví dụ:

Input:

2

1 5

7 10

Output:

4

2

Giải thích: Từ 1 đến 5 có 4 số đặc biệt là: 2, 3, 4, 5. Từ 7 đến 10 có 2 số đặc biệt là: 7, 9.

Ràng buộc:

● 30% số điểm tương ứng với Q ≤ 100 và R ≤ 1000.

● 40% số điểm tương ứng với Q ≤ 10^5 và R ≤ 10^5.

● 30% số điểm tương ứng với Q ≤ 10^5 và R ≤ 10^6.

Trong một phòng thí nghiệm, các nhà khoa học xây dựng một hệ sinh thái gồm nhiều thực thể trí tuệ nhân tạo. Mỗi thực thể được gán một cấp độ năng lự có n thực thể và tất cả đều ở cấp độ 1. Quá trình tiến hóa của hệ sinh thái diễn ra trong k ngày, ở mỗi ngày các thực thể đang tồn tại thực hiện lần lượt hai bước sau:

● Thứ nhất: Mỗi thực thể đang ở cấp độ i tạo ra đúng i thực thể mới có cấp độ 1. Các thực thể mới được tạo ra trong ngày này chỉ bắt đầu tham gia quá trình tiến hóa từ ngày kế tiếp.

● Thứ hai: Sau khi quá trình tạo mới kết thúc, mỗi thực thể đã tồn tại từ đầu ngày sẽ tăng cấp từ i lên i + 1.

Yêu cầu: Hãy xác định sau đúng k ngày hệ sinh thái có tổng cộng bao nhiêu thực thể. Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho 10^9 + 7.

Dữ liệu vào: Đọc từ tệp TIENHOA.INP gồm một dòng duy nhất chứa hai số nguyên n và k (1 ≤ n ≤ 10^3, 1 ≤ k ≤ 10^5).

Dữ liệu ra: Ghi ra tệp TIENHOA.OUT một số nguyên duy nhất là số lượng thực thể có trong hệ sinh thái sau đúng* k* ngày (đã chia lấy dư cho 10^9 + 7).

Ví dụ:

Input:

5 3

Output:

65

Ràng buộc:

● 40% số điểm tương ứng với n ≤ 100, k ≤ 10^3.

● 60% số điểm còn lại không có ràng buộc gì thêm.