Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sheldon's Obtuse Triangle

By fire_tornado · Limits 1s, 512 MB

We all know Sheldon Cooper from The Big Bang Theory. Recently he got his Nobel Prize. He likes polygons and circles so much. He has a question about polygons and circles for you.

Suppose there is a regular N-sided polygon inscribed in a circle. From there Sheldon can randomly choose any three distinct points. Now he wonders what is the probability that chosen points form an obtuse triangle.

It can be shown that, this probability can be represented by P / Q, where P and Q are coprime integers, and Q ≠ 0 mod (109 + 7). You have to print the value of P . Q-1 mod (109 + 7).

Input

First line of the input contains an integer T(1 ≤ T ≤ 105) which denotes the number of test cases. Then for each test case, there will be an integer N(3 ≤ N ≤ 1018).

Output

For each test case, print the case number as “Case X: ” and then a single integer probability that chosen points form an obtuse triangle.

Sample

InputOutput
2
3
5
Case 1: 0
Case 2: 500000004

An obtuse triangle is a triangle that has one angle greater than 90°.


Discussion
Statistics

52% Solution Ratio

ovis96Earliest, 1M ago

ovis96Fastest, 0.1s

NJRafiLightest, 2.2 MB

theunownShortest, 758B

Submit

Login to submit