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

然而，这个测试对于一些数学博士生甚至一些教授来说都很难。因此，数学系想编写一个辅助程序来解决这个任务（这并不荒唐，因为他们打算通过出售该程序来赚钱）。

给任何访问数学系首页的人呈现的任务如下：给定一个自然数 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

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

第一行包含查询数量 t（t \le 10^6）。

每个查询包含一个自然数 n（1 \le n \le 10^6）。

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