Số nguyên dương \(n\) được gọi là đẹp nếu thỏa mãn hai điều kiện sau:

• \(n\) là số lẻ.

• \(n\) và \(\frac{n + 1}{2}\) là số nguyên tố.

Ví dụ: \(n = \ 5\) là số đẹp vì \(5\)5 là số lẻ, \(n\ = \ 5\) và \(\frac{n + 1}{2} = 3\) là số nguyên tố.

Yêu cầu: Cho \(q\) câu hỏi, câu hỏi thư \(i\) gồm hai số nguyên \(l_{i},\ r_{i}\), cho biết có bao nhiêu số đẹp trong các số từ \(l_{i}\) đến \(r_{i}\)

Dữ liệu vào:

+ Dòng 1 chứa số nguyên \(q\ (1 \leq \ q\ \leq \ 10^{5})\).

+ \(q\) dòng sau: dòng thứ \(i\) gồm hai số nguyên \(l_{i},\ r_{i}\ \ (1 \leq \ l_{i}\ \leq \ r_{i}\ \ \leq 10^{6})\)

Kết quả:

+ Gồm \(q\) dòng, dòng thứ \(i\) là kết quả câu hỏi thứ \(i\).

Ví dụ: