Định đề Bertrand 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<=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 [n+1;2n].

Input

- Dòng 1: số T (T<=10⁶)là số bộ dữ liệu

- n 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<=10⁶.

Output

- Ghi số lượng số nguyên tố trong đoạn tương ứng với dữ liệu vào.