마법처럼 경이로운 견학

한 전자제품 공장의 수수께끼 같은 주인이 매우 흥미로운 일을 하기로 했다. 그녀는 일곱 개의 전자 기기 안에 황금 트랜지스터를 숨겼고, 그 기기들을 구매한 사람들은 마법처럼 경이로운 공장 견학에 초대된다.

Arnar와 Solveig는 동네 전자제품 매장의 한 기기 안에 황금 트랜지스터가 숨겨져 있다는 정보를 입수했다. 먼저 두 사람은 돈을 모아 모든 기기를 산 다음, 기기들을 일직선으로 놓고 0부터 N-1까지 번호를 매겼다. 각 기기에는 일정한 수의 트랜지스터가 들어 있다. 그런 다음 두 사람은 누가 황금 트랜지스터를 가질지 결정하기 위한 전략에 합의했다.

먼저 Arnar가 기기들의 구간 [a, b](양 끝 포함)를 선택하며, 이때 0 ≤ a ≤ b < N이다. 다음으로 Solveig는 자신이 가져갈 기기 집합 하나를 다음 중에서 선택한다.

• a > 0이면 구간 [0, a-1]의 모든 기기를 가져갈 수 있다.

• b < N-1이면 구간 [b+1, N-1]의 모든 기기를 가져갈 수 있다.

• 언제나 구간 [a, b]의 모든 기기를 가져가는 것을 선택할 수 있다. Solveig가 기기 집합 중 하나를 선택하면, Arnar는 그녀가 가져가지 않은 모든 기기를 가져간다.

예를 들어 기기가 3개이고 Arnar가 구간 [1, 1]을 선택하면, Solveig는 구간 [0, 0], 구간 [1, 1], 구간 [2, 2] 중 하나를 가져갈 수 있다. 반면 Arnar가 구간 [1, 2]을 선택하면 Solveig는 구간 [0, 0] 또는 구간 [1, 2]을 가져갈 수 있다.

각 기기에 들어 있는 트랜지스터의 수가 주어지고, Arnar와 Solveig가 각각 황금 트랜지스터를 얻을 확률을 최대화하려고 할 때(이 확률은 트랜지스터 수가 최대가 되도록 전자 기기를 가져가면 최대화된다), Arnar가 황금 트랜지스터를 얻어 마법처럼 경이로운 견학에 당첨될 확률은 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ p ≤ $10^{6}$. 1 ≤ q ≤ $10^{6}$. 1 ≤ r ≤ $10^{6}$. 1 ≤ s ≤ $10^{6}$.

작은 데이터 세트

시간 제한: 60초. 1 ≤ N ≤ 1000.

큰 데이터 세트

시간 제한: 120초. 1 ≤ N ≤ $10^{6}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 N, p, q, r, s의 다섯 수가 주어진다. 이는 기기가 N개 있고, i^{th} 기기에 ((i * p + q) MOD r + s)개의 트랜지스터가 들어 있음을 나타낸다. 기기 번호는 0부터 N-1까지임을 기억하라.

각 테스트 케이스마다 "Case #x: y"이 포함된 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Arnar가 마법처럼 경이로운 견학에 당첨될 확률이다.

y가 정답과 절대 오차 또는 상대 오차가 10^{-9} 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ을 참조하라.

마지막 예제 테스트 케이스는 작은 데이터 세트의 제한을 충족하지 않는다는 점에 유의하라. 작은 데이터 세트에서는 올바른 풀이가 마지막 예제 테스트 케이스에서 오답을 반환하거나 실행 시간이 매우 길어질 수도 있다.

예제 테스트 케이스 설명

첫 번째 예제 테스트 케이스에는 트랜지스터 하나가 든 전자 기기 하나가 있다. Arnar는 구간 $[0, 0]$을 선택해야 하고, Solveig는 구간 $[0, 0]$의 모든 기기를 가져가야 한다. Arnar가 마법처럼 경이로운 견학에 당첨되는 것은 불가능하다.

두 번째 예제 테스트 케이스에는 전자 기기가 열 개 있으며, 각각의 트랜지스터 수는 다음과 같다: [2, 5, 1, 4, 7, 3, 6, 2, 5, 1]. Arnar는 7개와 3개의 트랜지스터가 든 기기들을 포함하는 구간 $[4, 5]$을 선택한다. Solveig는 6개, 2개, 5개, 1개의 트랜지스터가 든 기기들을 포함하는 구간 $[6, 9]$을 선택한다. 그러면 Arnar에게 처음 여섯 개의 기기가 남고, Arnar가 견학에 당첨될 확률은 22/36이다.

세 번째 예제 테스트 케이스의 기기에는 각각 101개와 1개의 트랜지스터가 들어 있다.

네 번째 예제 테스트 케이스에서 각 기기의 트랜지스터 수는 다음과 같다: [103, 120, 114, 108, 102, 119, 113, 107, 101, 118, 112, 106, 100, 117, 111, 105, 122, 116, 110, 104].

다섯 번째 예제 테스트 케이스에서 각 기기의 트랜지스터 수는 다음과 같다: [1999999, 1999998, 1999997, 1999996, 1999995, 1999994, 1999993, 1999992, 1999991, 1999990].

여섯 번째 예제 테스트 케이스에서는 두 기기 모두 트랜지스터가 1개 들어 있다.

일곱 번째 예제 테스트 케이스에서 각 기기의 트랜지스터 수는 다음과 같다: [100, 1, 2].