Độ khó: Dễ (1/4 điểm)

Trong giờ học môn Toán, thầy giáo đưa ra quy ước "Số đặc biệt" là số nguyên dương có đúng $4$ ước số dương. Ví dụ: $8$ có $4$ ước số dương gồm $1, 2, 4, 8$ nên $8$ được gọi là số đặc biệt; $25$ có $3$ ước số dương gồm $1, 5, 25$ nên $25$ không phải là số đặc biệt.

Thầy giáo cho mỗi bạn hai số nguyên dương $L, R$ ($L < R \le 10^6$). Yêu cầu mỗi bạn đếm số lượng số đặc biệt trong đoạn $[L; R]$ (số $x$ nằm trong đoạn $[L; R]$ khi và chỉ khi $L \le x \le R$).

Yêu cầu

Hãy lập trình giúp các bạn đếm số lượng các số đặc biệt trong đoạn $[L; R]$.

Dữ liệu vào

• Dòng thứ nhất ghi số nguyên dương $T$ ($T \le 10^6$) là số lượng cặp số nguyên dương $L, R$.
• $T$ dòng tiếp theo mỗi dòng ghi hai số nguyên dương $L, R$.

Kết quả

Ghi ra $T$ dòng, mỗi dòng ghi số lượng các số đặc biệt trong đoạn $[L; R]$ tương ứng.

Giới hạn

• $60\%$ số test ứng với $T \le 10^2$, $R \le 10^3$;
• $30\%$ số test ứng với $10^2 < T \le 10^3$, $R \le 10^5$;
• $10\%$ số test ứng với $10^3 < T \le 10^6$, $R \le 10^6$.

Lưu ý: Tuy đề thi gốc cho phép đọc/ghi file, nhưng trên web thì mặc định là đọc dữ liệu từ bàn phím (stdin) và in kết quả ra màn hình (stdout).

Sample Input

3
6 9
10 15
20 33

Sample Output

2
3
5

Giải thích

• Từ $6$ đến $9$ có $2$ số đặc biệt là: $6$ và $8$.
• Từ $10$ đến $15$ có $3$ số đặc biệt là: $10, 14, 15$.
• Từ $20$ đến $33$ có $5$ số đặc biệt là: $21, 22, 26, 27, 33$.

Độ khó: Trung bình (2/4 điểm)

Nhân dịp tổng kết năm học, câu lạc bộ Tin học của bạn Nam tổ chức chuyến tham quan dã ngoại tại một khu du lịch trên địa bàn huyện X. Trải nghiệm đầu tiên của các bạn là trò chơi "Tìm kho báu". Để tìm ra kho báu các bạn cần phải có mật mã là một dãy $S$ gồm các chữ cái in thường. Mật mã này đã được mã hóa thành dãy $T$ theo quy tắc sau:

• Chọn trước $1$ ký tự $ch$ và tiến hành loại bỏ tất cả các ký tự $ch$ trong dãy $S$ thu được dãy mới là $K$.
• Nối dãy $K$ vào sau dãy $S$ thu được dãy $T$.

Các thành viên câu lạc bộ được Ban tổ chức cung cấp dãy $T$ và một ký tự $ch$. Nhiệm vụ của các thành viên là giải mã để tìm dãy $S$.

Yêu cầu

Tìm dãy $S$ từ dãy $T$ đã cho.

Dữ liệu vào

• Dòng thứ nhất ghi dãy $T$ có độ dài $L$ ($2 \le L \le 10^6$).
• Dòng thứ hai ghi một ký tự $ch$.

Kết quả

Ghi ra một dòng là dãy $S$ nếu tìm được mật mã, ngược lại ghi $-1$ nếu không tìm được mật mã.

Giới hạn

• $60\%$ số test ứng với $2 \le L \le 10^3$;
• $40\%$ số test ứng với $10^3 < L \le 10^6$.

Lưu ý: Tuy đề thi gốc cho phép đọc/ghi file, nhưng trên web thì mặc định là đọc dữ liệu từ bàn phím (stdin) và in kết quả ra màn hình (stdout).

Sample Input 1

abcab
c

Sample Output 1

abc

Sample Input 2

abcabcc
b

Sample Output 2

-1

Độ khó: Trung bình (2/4 điểm)

Bình và An đang tích cực học tập, ôn luyện để thi vào trường THPT chuyên trong tỉnh. Trong quá trình giải các bài toán, Bình đã gặp và giải một bài toán rất thú vị. Bình quy ước "Số đẹp" là số không chứa chữ số $0$ tận cùng. Bình muốn thử năng lực học tập của An nên thách đố An giải bài toán sau:

Cho hai số nguyên dương $a, b$ ($a < b$). Đặt $S = a \times (a+1) \times \dots \times b$. Hãy cho biết số lượng chữ số $0$ tận cùng của $S$ cần xóa để $S$ trở thành một số đẹp.

Ví dụ: Với $a = 4$, $b = 15$ thì $S = 4 \times 5 \times 6 \times \dots \times 15 = 217945728000$ nên số lượng chữ số $0$ tận cùng cần xóa là $3$.

Rất nhanh chóng An đã tìm ra kết quả, em hãy lập trình để cùng bạn An đối sánh kết quả với Bình nhé!

Yêu cầu

Đếm số lượng số $0$ tận cùng của $S$ cần xóa để $S$ trở thành số đẹp.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên $T$ ($1 \le T \le 10^5$) là số lượng cặp số nguyên.
• $T$ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương $a, b$ ($a < b \le 10^{16}$).

Kết quả

Ghi ra $T$ dòng, mỗi dòng ghi số lượng chữ số $0$ tận cùng của $S$ tương ứng. Kết quả có thể rất lớn nên cần chia lấy dư cho $10^9 + 7$ trước khi ghi ra.

Giới hạn

• $40\%$ số test ứng với $1 \le T \le 10$, $a < b \le 18$;
• $30\%$ số test ứng với $T = 1$, $a < b \le 10^5$;
• $20\%$ số test ứng với $1 < T \le 10^4$, $a < b \le 10^5$;
• $10\%$ số test ứng với $10^4 < T \le 10^5$, $a < b \le 10^{16}$.

Lưu ý: Tuy đề thi gốc cho phép đọc/ghi file, nhưng trên web thì mặc định là đọc dữ liệu từ bàn phím (stdin) và in kết quả ra màn hình (stdout).

Sample Input

4
1 6
1 10
2 4
10 20

Sample Output

1
2
0
3

Giải thích

• Tích $1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720$, kết quả là $1$.
• Tích $1 \times 2 \times 3 \times \dots \times 10 = 3628800$, kết quả là $2$.
• Tích $2 \times 3 \times 4 = 24$, kết quả là $0$.
• Tích $10 \times 11 \times \dots \times 20 = 6704425728000$, kết quả là $3$.

Độ khó: Khá (3/4 điểm)

Tuấn được công ty giao cho nhiệm vụ theo dõi giá trị cổ phiếu của công ty mình đang làm việc. Thời gian theo dõi giá trị cổ phiếu trong $n$ ngày. Ngày thứ $i$ có giá trị cổ phiếu là $ai$ ($ai \le 10^5$).

Ngày thứ $i$ được gọi là tăng trưởng nếu có giá trị cổ phiếu lớn hơn ngày thứ $j$ ở trước đó. Tức là tồn tại chỉ số $j$ sao cho $j < i$ và $aj < ai$. Đối với ngày thứ $i$, gọi $j$ là ngày xa nhất ở phía trước và có giá trị cổ phiếu thấp hơn ngày thứ $i$. Độ tăng trưởng của ngày thứ $i$ được tính là số ngày đứng giữa ngày đó và ngày thứ $j$ (có tính ngày thứ $j$), tức là bằng $i - j$. Nếu ngày thứ $i$ không tăng trưởng thì độ tăng trưởng bằng $0$.

Yêu cầu

Tính độ tăng trưởng của mỗi ngày trong các ngày Tuấn đang theo dõi.

Dữ liệu vào

• Dòng thứ nhất ghi số nguyên dương $n$.
• Dòng thứ hai ghi dãy số nguyên dương $a1, a2, \dots, a_n$.

Kết quả

Ghi ra một dòng gồm $n$ giá trị là độ tăng trưởng của các ngày theo dõi tương ứng, các số cách nhau một dấu cách.

Giới hạn

• $30\%$ số test ứng với $0 < n \le 5 \times 10^5$;
• $70\%$ số test ứng với $5 \times 10^5 < n < 5 \times 10^6$.

Lưu ý: Tuy đề thi gốc cho phép đọc/ghi file, nhưng trên web thì mặc định là đọc dữ liệu từ bàn phím (stdin) và in kết quả ra màn hình (stdout).

Sample Input 1

6
10 8 5 3 9 45

Sample Output 1

0 0 0 0 3 5

Giải thích 1

Đối với ngày thứ $3$: $a_3 = 5$, không có ngày nào trước ngày đó có giá trị cổ phiếu thấp hơn, nên độ tăng trưởng của ngày thứ $3$ là $0$.

Sample Input 2

7
16 4 6 3 2 18 15

Sample Output 2

0 0 1 0 0 5 5

Giải thích 2

Đối với ngày cuối cùng $a_7 = 15$, ngày thứ $j$ trước ngày đó xa nhất và có giá trị cổ phiếu thấp hơn là ngày thứ $2$, nên độ tăng trưởng của ngày cuối cùng là $5$.