Số nguyên tố

Trong ngày thực tập đầu tiên, thầy Hải có một câu đố nho nhỏ cho các học sinh của mình. Cho một số nguyên \(n\), hãy kiểm tra \(n\) có phải là số nguyên tố hay không?

Số nguyên tố là số tự nhiên lớn hơn 1 chỉ có hai ước số dương phân biệt là 1 và chính nó.

Input:

• Gồm một dòng duy nhất là số nguyên \(n (|n| \le 10^{12})\)

Output:

• In ra YES nếu \(n\) là số nguyên tố. Ngược lại in ra NO.

Example

9

NO

7

YES

Hãy tìm tất cả các số nguyên tố trong đoạn [\(A;B\)]

Input

• Gồm 2 số nguyên \(A;\ B\) cách nhau bởi 1 dấu cách (\(1\leq A\leq B\leq 10^7\))

Output

• Ghi ra tất cả các số nguyên tố trong khoảng [\(A;B\)]. Mỗi số trên 1 dòng.

Example

1 10

2
3
5
7

Hôm nay coder bin9638 top 1 thế giới nhận lời thách đấu của coder thứ 7 tỉ thế giới algorit solo giải 1 bài toán do giáo sư nhphucqt đưa ra.

Bài toán là cho 2 số tự nhiên \(l,r\). Hãy đếm số lượng số nguyên tố giữa chúng.

bin9638 loay hoay mãi mà vẫn chưa nghĩ ra cách làm trong khi algorit đã sắp xong, các bạn hãy giúp bin9638 chiến thắng trong cuộc solo này nhé. Nếu giải được thì bin9638 sẽ chia 1 nửa phần thưởng của cuộc solo này cho các bạn đó !

- Yêu cầu: đếm số lượng số nguyên tố trong đoạn \([l,r]\)

Input

• Dòng đầu tiên chứa số nguyên dương \(q\) là số đoạn \([l,r]\)
• \(q\) dòng tiếp theo mỗi dòng chứa \(2\) số nguyên dương \(l\) và \(r\)

Output

• Gồm \(q\) dòng, dòng thứ \(i\) ghi một số là số các số nguyên tố trong đoạn \([l,r]\) thứ \(i\) đã cho.

Constraints

• \(1 \leq l,r \leq 2 \times 10^8\)
• \(1 \leq q \leq 10^5\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(q \leq 10^3\), \(l\) và \(r \leq 10^7\)
• Subtask \(2\) (\(50\%\) số điểm): \(q \leq 10^5\), \(l\) và \(r \leq 2 \times 10^8\)

Example

1
2 5 

3