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).
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).
For each test case, print the case number as “Case X: ” and then a single integer probability that chosen points form an obtuse triangle.
| Input | Output |
|---|---|
2 3 5 | Case 1: 0 Case 2: 500000004 |
An obtuse triangle is a triangle that has one angle greater than 90°.