YAPTCHA

Time limit1sMemory limit128 MB

Summary

For each query n, compute the sum of floor(((3k+6)!+1)/(3k+7) - floor((3k+6)!/(3k+7))) over k from 1 to n. The sum equals the count of primes among 3k+7 for k=1..n, so precompute primes up to 3n+7 and prefix counts.

Level: Hard8 of 10
Topics: Number theory, Math, Prefix sum, Brute force
Solved: No attempts yet

Problem

Every time Seonyeong solves a problem, she posts the solution method to her Practice Log. The site became so popular that a million people visit it every day.

Seonyeong dislikes people who copy only the source code and submit it to an online judge without reading the explanation. To stop this, she decided to add a Yet-Another-Public-Turing-test-to-tell-Computers-and-Humans-Apart (YAPTCHA) to her homepage.

This YAPTCHA is so hard that even students with a PhD or professors cannot solve it easily. Sanggeun, who wants to read the solutions, wants to write a program that solves the test automatically.

When you visit the homepage, you are given a natural number $n$ together with the following expression. If you compute its value $S_n$ and enter it, you can view the solution. Given $n$ , write a program that computes $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

Here $\lfloor x \rfloor$ denotes the greatest integer not greater than $x$ (the floor of $x$ ).

Input

The first line contains the number of queries $t$ ( $t \le 10^6$ ). Each of the following queries is given on its own line and consists of a single natural number $n$ ( $1 \le n \le 10^6$ ).

Output

For each query $n$ , print $S_n$ on its own line.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
1
1
```
Expected output
```
0
```