Pia's Party

Pia wants to set up the audio system for her birthday party. The party will take place on a circular area, because Pia believes a circle is the most beautiful two-dimensional shape. Pia has four loudspeakers that she can place on certain points along the circle's circumference. From her extensive party experience she knows that people will only dance in the region enclosed by the four loudspeakers. Because she wants the dance floor to be as large as possible, she wants to maximize the area of the quadrilateral defined by the four loudspeakers. Can you help Pia?

You are given a circle of diameter $d$ with $n$ points equally spaced around its circumference. The points are numbered in order around the circle as $0, 1, 2, \dots, n-1$. Of these $n$ points, $c$ are suitable for placing loudspeakers. These points are given by the generator function $(g \cdot k) \bmod n$ for $k \in \{0, 1, 2, \dots, c-1\}$. Given the integers $d$, $n$, $c$, and $g$, compute the largest area that can be formed by placing four loudspeakers on suitable points.

The first line contains the number of scenarios.

Each scenario consists of a single line containing four space-separated integers, whose meanings are, in order:

• the diameter $d$ of the circle ($1 \le d \le 1000$);
• the number $n$ of points on the circle ($4 \le n \le 10^9$);
• the number $c$ of points suitable for loudspeakers ($4 \le c \le 1000$ and $c \le n$);
• the number $g$ for the generator function ($1 \le g \le n$), which is relatively prime to $n$ (that is, they share no common divisor greater than 1).

For each scenario, first print a line of the form Scenario #i:, where $i$ is the scenario number starting from 1.

Then print a single line with the maximum area Pia can achieve for her dance floor, rounded to six decimal places. Separate two consecutive scenarios with a single blank line.