题目描述

给定 $n \leq 10^6$，求 $S_n$ 的值，其中：

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

输入格式

第一行一个整数 $t \ ( 1 \le t \le 10^6)$，表示下来 $t$ 组数据。每组数据一个整数 $n \ (1 \le n \le 10^6)$。

输出格式

一行一个整数 $S_n$。

输入样例

13
1
2
3
4
5
6
7
8
9
10
100
1000
10000

输出样例

0
1
1
2
2
2
2
3
3
4
28
207
1609