Bài tập

Có \(k\) truy vấn, mỗi truy vấn cho hai số nguyên dương \(a \le b\). Với mỗi truy vấn, hãy đếm số các số nguyên tố trong đoạn \([a, b]\).

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à số lượng số nguyên tố trong đoạn của truy vấn thứ \(i\).

Constraints

• \(1 \le k \le 5\).
• \(1 \le a \le b \le 10^8\).

Sample Input

2
3 12
14 16

Sample Output

4
0

Explanation

Trong đoạn \([3, 12]\) có các số nguyên tố \(3, 5, 7, 11\). Đoạn \([14, 16]\) không có số nguyên tố nào.

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
(())
()
()()