Định đề Bertrand là một định lý phát biểu rằng với bất kỳ số nguyên \(n>3\), luôn tồn tại ít nhất một số nguyên tố \(p\) sao cho \(n<p<2n-2\)

Yêu cầu

Cho \(n\), đếm số lượng số nguyên tố thuộc đoạn \([n+1;2n]\)

Dữ liệu

• Dòng 1 ghi số T là số bộ dữ liệu \((0<T \leq 10^6)\)

• \(T\) dòng tiếp theo, mỗi dòng ghi số nguyên n tương ứng \((0<n \leq 10^6)\)

Kết quả

• 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

Ví dụ

INPUT

1
548814

OUTPUT

40321