NAJSQ - Square

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:

Input

Output

3
2
3
4

Case 1: 4
Case 2: 13
Case 3: 29


Added by:Najmuzzaman
Date:2014-10-25
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-11-01 16:29:41 ivar.raknahs
@Bhavuk Arora =>u should have the knowledge of inverse modulus to check the overflow .
try this
for n=
1=>0
12345678 => 159822696
98765432 => 996572846
1000000000 => 999999915
343443234 => 145101462
999999999 => 999999866

Last edit: 2014-11-01 16:37:05
2014-11-01 11:27:21 Bhavuk Arora
i am getting WA repeatedly. I have checked for the overflow condition in c++. Any tricky case?
Submission ID 12786386. Can you please check whats wrong?

Last edit: 2014-11-01 13:20:10
2014-10-31 13:50:27 SD
I am getting WA repeatedly. Is there any trick in output pattern ? Can anyone tell me ?
2014-10-30 10:05:51 SK
very easy......

Last edit: 2014-11-02 05:00:20
2014-10-30 10:05:51 ivar.raknahs
please try to solve this with c++.
It's easy with python but require some knowledge for c++ (as ans will overflow).
Just go for c++.
2014-10-30 10:05:51 nitish rao
Easy one!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.