Định đề Bertrand được phát biểu bởi nhà toán học Pháp Joseph Louis Bertrand (1882-1903). Định đề như sau: Với một số tự nhiên \(n > 0\) luôn tồn tại một số nguyên tố \(p\) mà \(n < p \leq 2n\).

Yêu cầu: Cho \(n\), kiểm tra định đề Bertrand bằng cách đếm số lượng số nguyên tố nằm trong đoạn \(\lbrack n + 1,\ 2n\rbrack\).

Dữ liệu vào:

+ Dòng đầu ghi số nguyên \(T\ \)là số bộ dữ liệu;

+ \(T\) dòng sau, mỗi dòng tương ứng là một bộ dữ liệu, mỗi dòng chứa một số nguyên \(n \leq 10^{6}\).

Kết quả:

+ Gồm \(T\) dòng, mỗi dòng chứa một số nguyên là số lượng số nguyên tố trong đoạn tương ứng với dữ liệu vào.

Ví dụ:

Input	Output		Input	Output
1 2	1		2 1 3	1 1