A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles. It is also a polygon such that rotating about its centre by 90 degrees gives the same polygon. It is not the only polygon with the latter property, however, as a regular octagon also has this property.

Sajib is little boy read in a school. Just learn drawing square. He draw square in many type of  length. When he draw a square he also connect  all the point in side of the square. And found a interesting properties. There have also some small Square inside the Square. If he draw a square length 2, he found 4 small square inside the Square. Today he draw a n length square. But feel so boring to count the small square. Now he want to give you the task.

Fig: Square

Sajib given the length of Square. You tell him some many small square inside it. A square said to be small square if it’s length is smaller than real Square.

Input:

The input first line consists of a number T (1 ≤ T ≤ 10000) test cases. Each test case starts with the integer n (1 <= n <= 10^9). Where n is the length of Square.

Output:

For each case print one line: Case X: S, where X is the case number and S is number of small square. There is no new-line between cases.

The S may be to large which not fit in integer so mod it with 10^9+7.

Sample: