Để truy cập vào kho dữ liệu cốt lõi của trung tâm Học Công Nghệ, hệ thống yêu cầu bạn phải nhập vào một khóa bảo mật. Khóa này chính là số lượng các số nguyên tố nằm trong đoạn từ L đến R. Hãy viết chương trình đếm số lượng số nguyên tố trong đoạn này thật nhanh để kịp thời gian mở khóa.

Input: Một dòng duy nhất chứa hai số nguyên L và R (1 <= L <= R <= 10^6).

Output: In ra số lượng số nguyên tố nằm trong đoạn [L, R].

Ví dụ:

Input:

10 20

Output:

4

(Giải thích: Các số nguyên tố là 11, 13, 17, 19).

Một chip nhớ đang lưu trữ một con số khổng lồ dưới dạng xâu ký tự S. Do dung lượng bị đầy, hệ thống yêu cầu bạn phải xóa đi đúng K chữ số khỏi S. Lập trình viên cần chọn các chữ số để xóa sao cho con số tạo thành từ các chữ số còn lại (giữ nguyên thứ tự ban đầu) là lớn nhất có thể.

Input:

Dòng 1: Hai số nguyên N và K (1 <= K < N <= 10^5), với N là chiều dài xâu S.

Dòng 2: Xâu S chứa N chữ số (từ 0 đến 9).

Output: Con số lớn nhất sau khi xóa đúng K chữ số.

Ví dụ:

Input:

4 2
1924

Output:

94

Huấn luyện viên cần chọn ra hai vận động viên từ đội tuyển gồm N người để tham gia nội dung thi đấu đôi. Chỉ số sức mạnh của người thứ i là A_i. Để hai người có thể bổ trợ chiến thuật tốt nhất, hiệu số sức mạnh của họ (người lớn hơn trừ người nhỏ hơn) phải đúng bằng X. Hãy đếm xem có bao nhiêu cặp vận động viên thỏa mãn điều kiện này.

Input:

Dòng 1: Hai số nguyên N và X (1 <= N <= 10^5, 0 <= X <= 10^9).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^9).

Output: Số lượng cặp thỏa mãn.

Ví dụ:

Input:

5 2
1 5 3 4 2

Output:

3

(Giải thích: Các cặp là (1,3), (3,5) và (2,4)).

Trong một tàn tích cổ, có N rương kho báu xếp thành một hàng ngang, rương thứ i chứa A_i đồng tiền vàng. Bạn được phép lấy toàn bộ số vàng trong một dải các rương liên tiếp nhau, với điều kiện tổng số vàng lấy được phải chia hết cho K (để chia đều cho K thành viên trong đội). Hãy tìm độ dài của dải rương liên tiếp dài nhất thỏa mãn điều kiện trên.

Input:

Dòng 1: Hai số nguyên N và K (1 <= N, K <= 10^5).

Dòng 2: N số nguyên Ai (0 <= Ai <= 10^9).

Output: Độ dài lớn nhất của đoạn con liên tiếp có tổng chia hết cho K. Nếu không có, in 0.

Ví dụ:

Input:

6 3
1 2 1 2 1 2

Output:

6