YAPTCHA

시간 제한1초메모리 제한128 MB

요약

각 질의 n에 대해 k=1부터 n까지 floor(((3k+6)!+1)/(3k+7) - floor((3k+6)!/(3k+7)))의 합을 구한다. 이 값은 3k+7 중 소수의 개수와 같으므로 3n+7까지의 소수를 미리 구해 누적 개수를 출력한다.

난이도: 어려움10점 중 8점
유형: 정수론, 수학, 누적 합, 완전 탐색
정답자: 아직 제출이 없습니다

문제

선영이는 문제를 풀 때마다 자신의 Practice Log에 풀이법을 올려놓는다. 이 사이트는 매우 유명해져서 하루에 백만 명이 방문하는 사이트가 되었다.

선영이는 풀이를 읽지 않고 소스 코드만 복사해 온라인 저지에 제출하는 사람들을 싫어한다. 이를 막기 위해 홈페이지에 Yet-Another-Public-Turing-test-to-tell-Computers-and-Humans-Apart(YAPTCHA)를 추가하기로 했다.

이 YAPTCHA 테스트는 매우 어려워서 박사 학위를 받은 학생이나 교수도 쉽게 풀지 못한다. 풀이를 보고 싶은 상근이는 이 테스트를 자동으로 푸는 프로그램을 만들려고 한다.

홈페이지에 접속하면 자연수 $n$ 과 함께 다음 식이 주어진다. 이 식의 값 $S_n$ 을 계산해 입력하면 풀이를 볼 수 있다. $n$ 이 주어졌을 때 $S_n$ 을 구하는 프로그램을 작성하시오.

S_n = \sum_{k=1}^{n} \left\lfloor \frac{(3k+6)! + 1}{3k+7} - \left\lfloor \frac{(3k+6)!}{3k+7} \right\rfloor \right\rfloor

여기서 $\lfloor x \rfloor$ 는 $x$ 보다 크지 않은 가장 큰 정수(바닥 함수)를 의미한다.

입력

첫째 줄에 쿼리의 수 $t$ ( $t \le 10^6$ )가 주어진다. 이어서 각 쿼리가 한 줄에 하나씩 주어지며, 각 쿼리는 자연수 $n$ ( $1 \le n \le 10^6$ ) 하나로 이루어져 있다.

출력

각 쿼리로 주어진 $n$ 에 대해 $S_n$ 을 한 줄에 하나씩 출력한다.

예제2

예제 1

입력

예상 출력

예제 2
입력
```
1
1
```
예상 출력
```
0
```