Tuyển sinh lớp 10 Chuyên tỉnh Nghệ An 2026

Trong tiết học môn Toán, lớp của bạn An được tìm hiểu về các số có tính chất đặc biệt. Giáo viên gọi số nguyên dương \(X\) là "Số đặc biệt" nếu khi chia \(X\) cho \(10\) có số dư đúng bằng khi chia \(X\) cho \(7\).

Ví dụ: \(X = 74\) là "Số đặc biệt" vì khi chia \(74\) cho \(10\) và \(74\) cho \(7\) có cùng số dư là \(4\).

Giáo viên yêu cầu đếm các "Số đặc biệt" trong đoạn \([L; R]\) cho trước. Rất nhanh chóng An đã tìm ra kết quả của bài toán. Em hãy viết chương trình để đối sánh với kết quả mà bạn An đã tìm được.

Yêu cầu: Với mỗi đoạn \([L; R]\), hãy đếm xem có bao nhiêu "Số đặc biệt" nằm trong đoạn đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) là số lượng đoạn truy vấn (\(1 \leq T \leq 10^5\)).
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L, R\) (\(1 \leq L \leq R \leq 10^{18}\)).

Output

• Ghi ra \(T\) dòng, mỗi dòng ghi một số nguyên là kết quả tương ứng với mỗi đoạn được truy vấn.

Example

2
1 20
74 200

6
10

Scoring

• \(70\%\) số test thỏa mãn: \(T \leq 10, R \leq 10^6\).
• \(20\%\) số test thỏa mãn: \(T \leq 10^3, R \leq 10^6\).
• \(10\%\) số test thỏa mãn: \(T \leq 10^5, 10^6 < R \leq 10^{18}\).

Trong một chuyến thám hiểm lăng mộ, các nhà khảo cổ học tìm thấy một chuỗi ký tự cổ (ký hiệu là \(T\)) gồm \(n\) ký tự chứa các chữ cái Latin và chữ số thập phân. Để tìm ra mật mã mở cửa mật thất, các nhà khảo cổ cần giải mã hai thông tin quan trọng ẩn giấu trong chuỗi ký tự này:

• Chỉ số năng lượng: là số lượng các ký tự số có trong chuỗi \(T\);
• Chìa khóa tối thượng (\(P\)): là số nguyên tố có giá trị lớn nhất được trích xuất từ tất cả các ký tự số liên tiếp trong chuỗi \(T\) và không có số \(0\) ở vị trí đầu.

Yêu cầu: Hãy giúp các nhà khảo cổ xác định hai thông tin trên để mở cửa mật thất.

Input

• Một dòng duy nhất chứa chuỗi ký tự \(T\).

Output

• Dòng đầu tiên ghi một số nguyên là số lượng ký tự số đếm được.
• Dòng thứ hai ghi giá trị của chìa khóa \(P\) (là số nguyên tố lớn nhất tìm được), nếu không tìm thấy ghi ra số \(0\).

Example

aB0011cd230d124ab17

12
17

M4ndnd8nd9nd15nd200

8
0

Constraints

• \(50\%\) số test thỏa mãn: \(n \le 255, P \le 10^3\).
• \(30\%\) số test thỏa mãn: \(n \le 10^6, P \le 10^6\).
• \(20\%\) số test thỏa mãn: \(n \le 5 \cdot 10^6, P \le 5 \cdot 10^6\).

Sau đợt lũ lụt, nhiều học sinh miền núi không còn đồ dùng học tập để đến trường. An và nhóm bạn trong lớp quyết định quyên góp tiền tiết kiệm để mua \(n\) gói đồ dùng học tập ủng hộ cho các bạn học sinh nói trên. Các gói đồ dùng được đánh số từ \(1\) đến \(n\), gói thứ \(i\) có giá là \(v_i\).

Thấy An và các bạn là người tốt, ông chủ cửa hàng đã áp dụng chương trình khuyến mãi đặc biệt dành cho các bạn. Ông cho phép nhóm bạn An chia \(n\) gói đồ dùng học tập trên thành một hoặc nhiều kiện hàng, mỗi kiện hàng gồm một hoặc nhiều gói. Đối với kiện hàng có nhiều hơn một gói thì giá chênh lệch giữa hai gói bất kỳ không bé hơn \(k\). Với mỗi kiện hàng chia được, nhóm bạn An chỉ phải thanh toán số tiền của gói đồ dùng học tập đắt nhất trong kiện hàng đó.

Yêu cầu: Hãy giúp nhóm bạn An chia \(n\) gói đồ dùng học tập thành các kiện hàng sao cho tổng số tiền phải trả là ít nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(k\) (\(n \leq 10^6, k \leq 10^5\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(v_1, v_2, \dots, v_n\) (\(v_i \leq 10^9\)).

Output

• Ghi ra một số nguyên duy nhất là tổng số tiền phải trả ít nhất.

Example

3 2
1 5 5

10

4 1
1 4 3 5

5

Scoring

• \(30\%\) số test thỏa mãn: \(n \leq 10^2\).
• \(30\%\) số test thỏa mãn: \(n \leq 10^4\).
• \(40\%\) số test không có ràng buộc gì thêm.

Anh Bình là một nhà đầu tư tham gia giao dịch trên sàn chứng khoán điện tử. Trên sàn đang niêm yết \(n\) mã giao dịch được sắp xếp thành một hàng và đánh số thứ tự từ \(1\) đến \(n\). Mã giao dịch thứ \(i\) được niêm yết với một giá trị lợi nhuận \(a_i\). Nhà đầu tư được hệ thống cấp phát \(m\) mã lệnh đánh số từ \(1\) đến \(m\). Mã lệnh thứ \(j\) chứa một số nguyên dương \(b_j\).

Anh Bình thực hiện lần lượt \(m\) lệnh tương ứng với các mã đã nhận, ở lượt thứ \(j\) anh chỉ được thực hiện một trong hai cách:

• Bỏ qua không sử dụng mã lệnh thứ \(j\);
• Dùng mã lệnh thứ \(j\) để chọn \(b_j\) mã giao dịch liên tiếp từ mã thứ \(i\) (\(1 \le i \le n\)), nếu đoạn \(i, i+1, \dots, i+b_j-1\) chưa từng được thực hiện trước đó.

Mỗi mã giao dịch chỉ được thực hiện nhiều nhất một lần. Anh Bình đã có chiến lược lựa chọn các mã lệnh một cách tối ưu nên thu được tổng lợi nhuận lớn nhất khi kết thúc giao dịch.

Yêu cầu: Hãy tìm ra tổng lợi nhuận lớn nhất của anh Bình khi kết thúc giao dịch.

Input

• Dòng đầu tiên ghi hai số nguyên dương \(n, m\) (\(1 \le n \le 10^5, 1 \le m \le 10^2\));
• Dòng thứ hai ghi \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^8\)) là giá trị lợi nhuận;
• Dòng thứ ba ghi \(m\) số nguyên dương \(b_1, b_2, \dots, b_m\) (\(b_j \le 10^5\)) là giá trị trên mã lệnh.

Output

• Ghi ra một số nguyên duy nhất là tổng lợi nhuận lớn nhất anh Bình đạt được.

Example

7 1
1 6 3 4 2 5 7
2

12

8 2
7 1 8 5 1 6 2 4
2 1

19

Scoring

• \(30\%\) số test thỏa mãn: \(m = 1, 1 \le n \le 10^5\).
• \(20\%\) số test thỏa mãn: \(m = 2, 1 < n \le 10^5\).
• \(50\%\) số test thỏa mãn: \(2 < m \le 10^2, 10^3 < n \le 10^5\).