피아의 파티

피아는 생일 파티를 위한 음향 시스템을 설치하려고 합니다. 피아는 원이 가장 아름다운 2차원 도형이라고 생각하기 때문에, 파티는 원 모양의 공간에서 열립니다. 피아는 원의 둘레 위 정해진 점에 놓을 수 있는 스피커 4개를 가지고 있습니다. 오랜 파티 경험을 통해, 사람들은 네 스피커로 둘러싸인 안쪽 영역에서만 춤을 춘다는 것을 알고 있습니다. 가능한 한 넓은 무대를 원하기 때문에, 피아는 네 스피커가 이루는 사각형의 넓이를 최대로 만들고 싶어 합니다. 피아를 도와줄 수 있나요?

지름이 $d$인 원의 둘레에 $n$개의 점이 같은 간격으로 놓여 있습니다. 점들은 원을 따라 순서대로 $0, 1, 2, \dots, n-1$로 번호가 매겨져 있습니다. 이 $n$개의 점 가운데 $c$개가 스피커를 놓기에 적합하며, 이 점들은 $k \in \{0, 1, 2, \dots, c-1\}$에 대해 생성 함수 $(g \cdot k) \bmod n$으로 주어집니다. 정수 $d$, $n$, $c$, $g$가 주어질 때, 적합한 점 중 4개에 스피커를 놓아 만들 수 있는 사각형의 최대 넓이를 구하세요.

첫째 줄에는 시나리오의 개수가 주어집니다.

각 시나리오는 공백으로 구분된 네 정수가 있는 한 줄로 이루어집니다. 각 수의 의미는 순서대로 다음과 같습니다.

• 원의 지름 $d$ ($1 \le d \le 1000$).
• 원 위의 점의 개수 $n$ ($4 \le n \le 10^9$).
• 스피커를 놓기에 적합한 점의 개수 $c$ ($4 \le c \le 1000$이고 $c \le n$).
• 생성 함수에 쓰이는 수 $g$ ($1 \le g \le n$). $g$는 $n$과 서로소입니다(즉, 1보다 큰 공약수를 갖지 않습니다).

각 시나리오에 대해, 먼저 Scenario #i: 형식의 줄을 출력합니다. 여기서 $i$는 1부터 시작하는 시나리오 번호입니다.

그다음 한 줄에 피아가 만들 수 있는 무대의 최대 넓이를 출력합니다. 이 넓이는 소수점 아래 여섯째 자리까지 반올림하여 출력합니다. 연속한 두 시나리오 사이는 빈 줄 하나로 구분합니다.