数学系最近遇到了一些麻烦。由于有大量未经授权的自动程序在爬取他们的网页，他们决定在网页上加入“又一个用于区分计算机和人类的公开图灵测试”（Yet-Another-Public-Turing-Test-to-Tell-Computers-and-Humans-Apart）。简而言之，为了获取他们的学术论文，人们必须证明自己有资格且有能力，即解决一个数学谜题。

然而，事实证明，这个测试对于一些数学博士生甚至一些教授来说都太难了。因此，数学系想要编写一个辅助程序来解决这个任务（这并非不合理，因为他们打算通过销售该程序来赚钱）。

任何访问数学系主页的人都会面临以下任务：给定一个自然数 $n$，计算：

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

其中 $[x]$ 表示不超过 $x$ 的最大整数。

输入格式

第一行包含询问的数量 $t$ ($t \le 10^6$)。

接下来的每行包含一个自然数 $n$ ($1 \le n \le 10^6$)，表示一次询问。

输出格式

对于输入中给出的每个 $n$，输出 $S_n$ 的值。

样例

输入样例 1

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

输出样例 1

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