Looks Like Giveway ?

This Problem is very straightforward. Let’s define a function $InvCnt(p)$ where $p$ is a permutation of length $n$. Definition of $InvCnt(p)$ is the minimum number of swaps needed to make the permutation $p$ sorted, and you are allowed to swap only adjacent elements.

A permutation is an array of length $n$, consisting of each of the integers from $1$ to $n$ in some order.

For example, a permutation of length $4$ is —

Then we need to do the following operations to sort the permutation —

So we need a total of $5$ swap operations to make $p$ sorted.

Now you are given an integer $n$. You have to print the total $sum$ of $InvCnt(p)$ for all permutations of length $n$. More formally, if we define a set $S$ consisting of all permutations of length $n$. Then we need to calculate

$$\displaystyle\sum_{p \in S} ^{}InvCnt(p) \mod 10^9+7$$

Input

Each set of tests contains multiple test cases.

The first line of the input contains a single integer $t$ — which represents the number of test cases.

Next, $t$ lines of the input contain a single integer $n$ — representing the length of the permutation.

$1\leq t \leq 10^6$

$1 ≤ n ≤  10^7$

Output

For each test case print the case number and a single integer  — the total $sum \mod 10^9 + 7$ from the problem statement.

Sample

Input	Output
4 3 2 4 17	Case 1: 9 Case 2: 1 Case 3: 72 Case 4: 941220792

Consider the first testcase.

For $n$ $=$ $3$. We have $6$ different permutations. And

$InvCnt(\{1,2,3\})$$=$$0$

$InvCnt(\{1,3,2\})$$=$ $1$

$InvCnt(\{2,1,3\})$$=$$1$

$InvCnt(\{2,3,1\})$$=$$2$

$InvCnt(\{3,1,2\})$$=$$2$

$InvCnt(\{3,2,1\})$$=$$3$

So $total sum$ is $0 + 1 + 1 + 2 + 2 + 3 = 9$