짧은 코드로 빠르게 많은 소수 세기

첫 줄에 테스트케이스의 개수 $T$가 주어진다. ($T \geq 1$)

각 테스트케이스마다 한 줄에 양의 정수 $N$이 하나씩 주어진다.

다음 조건 중 하나 이상이 성립한다.

• $T = 1$, $N \leq 10^{12}$
• $T \leq 100$, $N \leq 10^9$
• $T \leq 10^4$, $N \leq 10^6$

각 테스트케이스마다 한 줄에 $N$ 이하의 소수 개수를 출력한다.