YAPTCHA#5730
Sign in

YAPTCHA

1 second
128 megabytes
Very easy

The Faculty of Mathematics encountered a problem. Due to the large number of automated programs browsing their web pages, it was decided to restrict access to their scientific articles.

To gain access, one must now demonstrate their knowledge — namely, solve a mathematical problem.

However, the test turned out to be too difficult not only for graduate students, but even for some professors. Therefore, the faculty needs to develop a program that automatically solves this problem.

Visitors to the main page of the Faculty of Mathematics are given the following task: for a given positive integer , compute the value

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,

where denotes the greatest integer less than or equal to .

Input

The first line contains the number of queries t~(t \le 10^6).

Each of the following lines contains one integer n~(1 \le n \le 10^6).

Output

For each query, print the value of S_n on a separate line.

Examples

Example 1

Loading
Loading