Bài tập

Cho hai số nguyên dương \(a \le b\). Hãy đếm số các số nguyên tố nằm trong đoạn \([a, b]\).

Input

Một dòng chứa hai số nguyên \(a\) và \(b\).

Output

In ra một số nguyên là số lượng số nguyên tố trong đoạn \([a, b]\).

Constraints

• \(1 \le a \le b \le 10^9\).
• \(b - a \le 10^6\).

Sample Input

20 50

Sample Output

7

Explanation

Các số nguyên tố là \(23, 29, 31, 37, 41, 43, 47\).

Bạn được hỏi \(k\) câu hỏi, mỗi câu cho hai số nguyên dương \(a \le b\). Với mỗi câu, hãy cho biết trong đoạn \([a, b]\) có bao nhiêu số nguyên tố.

Input

• Dòng đầu chứa số nguyên \(k\).
• \(k\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\).

Output

In ra \(k\) dòng, dòng thứ \(i\) là câu trả lời cho câu hỏi thứ \(i\).

Constraints

• \(1 \le k \le 100\).
• \(1 \le a \le b \le 1\,000\,000\).

Sample Input

2
10 30
1 1

Sample Output

6
0

Explanation

Trong đoạn \([10, 30]\) có các số nguyên tố \(11, 13, 17, 19, 23, 29\). Đoạn \([1,1]\) không có số nguyên tố nào.

Dãy ngoặc đúng được định nghĩa đệ quy: xâu rỗng là dãy ngoặc đúng; nếu \(A\) đúng thì \((A)\) đúng; nếu \(A, B\) đúng thì \(AB\) đúng.

Cho xâu \(S\) chỉ gồm các ký tự ( và ). Bằng cách xóa đi một số ký tự bất kỳ (có thể không xóa) và giữ nguyên thứ tự các ký tự còn lại, ta thu được các xâu con. Hãy liệt kê tất cả các dãy ngoặc đúng khác rỗng và đôi một khác nhau có thể thu được.

Input

• Một xâu \(S\) khác rỗng, độ dài không quá \(20\), chỉ gồm ( và ).

Output

• Dòng đầu: số lượng dãy tìm được (in 0 nếu không có).
• Các dòng sau: từng dãy, theo thứ tự từ điển tăng dần (theo mã ASCII, ( < )).

Constraints

• \(1 \le |S| \le 20\)

Sample Input

(()(()

Sample Output

3
(())
()
()()

Một phần mềm lưu trữ dùng phương pháp mã hoá độ dài chạy để rút gọn văn bản: mỗi đoạn gồm các ký tự giống hệt nhau đứng liền kề được thay bằng số lần lặp viết liền trước ký tự đó. Số lần lặp luôn được viết ra, kể cả khi bằng \(1\). Ví dụ aaabbbbc được nén thành 3a4b1c.

Bạn cần cài đặt cả hai chiều: nén một xâu và giải nén một xâu đã nén.

Input

• Dòng 1: xâu \(S\) cần nén, chỉ gồm các chữ cái Latinh (hoa và thường phân biệt nhau).
• Dòng 2: xâu \(T\) đã ở dạng nén, gồm các cặp (số nguyên dương, chữ cái) viết liền nhau như trên.

Output

• Dòng 1: dạng nén của \(S\) (mỗi đoạn ký tự giống nhau tối đa liên tiếp được thay bằng số lần + ký tự).
• Dòng 2: xâu thu được sau khi giải nén \(T\).

Constraints

• \(1 \le |S|, |T| \le 10^6\).
• Xâu sau khi giải nén \(T\) có độ dài không quá \(10^6\).

Sample Input

wwwwkkkTT
3k1Z2m

Sample Output

4w3k2T
kkkZmm

Explanation

wwww kkk TT lần lượt thành 4w, 3k, 2T. Ở chiều ngược lại 3k là kkk, 1Z là Z, 2m là mm.