Yêu cầu:

Định đề Bertrand phát biểu rằng với bất kỳ số nguyên n, luôn tồn tại ít nhất một số nguyên tố P sao cho \(n+1<=p<=2n\) . Cho n, đếm số lượng số nguyên tố thuộc đoạn [\(n+1,2n\)] .

Dữ liệu vào:

• Dòng 1 ghi số T là số bộ dữ liệu\(t(t<=10^6)\) ,
• T dòng tiếp theo, mỗi dòng ghi số nguyên n tương ứng \(n(n<=10^6)\).

Dữ liệu ra:

gồm T dòng, mỗi dòng ghi số lượng số nguyên tố tương ứng với dữ liệu vào.

Input

10

Output

11