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

첫 줄에 테스트케이스의 개수 $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$ 이하의 소수의 개수를 출력한다.