Sheldon's Obtuse Triangle

fire_tornado 16th December Programming...
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°.

Submit

Login to submit.

Statistics

54% Solution Ratio
ovis96Earliest, Dec '19
Deshi_TouristFastest, 0.0s
NJRafiLightest, 2.2 MB
theunownShortest, 758B
Toph uses cookies. By continuing you agree to our Cookie Policy.