Description

Background

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

You are given a circle of diameter d, with n points equally spaced around the circumference. The points are numbered in order around the circle 0, 1, 2, . . . , n - 1. Of those n points, c of them are suitable for placing the loudspeakers on. These points are given by the generator function (g * k) mod n, for k in {0, 1, 2, . . . , c-1}. Given integers d, n, c, and g you are to compute the largest area that can be formed by placing four loudspeakers on suitable points.

Input

The first line contains the number of scenarios.

Every scenario consists of a single line containing four integers separated by a space. The meaning of these numbers are in order:

• The diameter d of the circle (1 <= d <= 1000).
  
• The number n of points on the circle (4 <= n <= 10⁹).
  
• The number c of suitable points for the loudspeakers (4 <= c <= 1000 and c <= n).
  
• The number g for the generator function (1 <= g <= n) which will be relatively prime to n (e.g. they do not have a common divisor greater than 1).

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1.

Then print a single line with the maximum area Pia can achieve for her dance floor. Print this area rounded to six decimal places. Every scenario is finished by a blank line.

4
10 13 4 3
20 31 6 5
1000 80000 50 3
100 1200 20 139

Scenario #1:
48.914286
Scenario #2:
179.100273
Scenario #3:
0.028490
Scenario #4:
4965.195940

Source

TUD Programming Contest 2005 (Training Session)

, Darmstadt, Germany

</p>