황금 트랜지스터와 공장 견학

전자제품 공장 주인이 기기 일곱 대 안에 황금 트랜지스터를 하나씩 숨겨 두었다. 그 기기를 산 사람은 공장 견학에 초대된다.

아르나르와 솔베이그는 동네 전자제품 가게에 있는 기기 한 대에 황금 트랜지스터가 들어 있다는 소식을 들었다. 둘은 돈을 모아 가게의 기기를 전부 사들인 다음, 일렬로 늘어놓고 0번부터 $N-1$번까지 번호를 붙였다. 기기마다 들어 있는 트랜지스터 개수는 다르다. 황금 트랜지스터는 가게 안 트랜지스터 가운데 하나이고 어느 것이든 똑같은 확률로 그 하나가 되므로, 어떤 사람이 황금 트랜지스터를 갖게 될 확률은 그 사람이 가진 트랜지스터 개수를 가게 전체 트랜지스터 개수로 나눈 값이다.

두 사람은 이렇게 나누기로 했다.

먼저 아르나르가 $0 \le a \le b < N$을 만족하는 구간 $[a, b]$를 하나 고른다. 양 끝 번호도 구간에 포함된다. 그다음 솔베이그가 아래 묶음 가운데 정확히 하나를 가져간다.

• $a > 0$이면 구간 $[0, a-1]$의 기기를 모두 가져갈 수 있다.
• $b < N-1$이면 구간 $[b+1, N-1]$의 기기를 모두 가져갈 수 있다.
• 구간 $[a, b]$의 기기는 언제든 모두 가져갈 수 있다.

솔베이그가 고르고 남은 기기는 아르나르가 전부 가진다.

예를 들어 기기가 3대이고 아르나르가 $[1, 1]$을 골랐다면 솔베이그는 $[0, 0]$, $[1, 1]$, $[2, 2]$ 중에서 고른다. 아르나르가 $[1, 2]$를 골랐다면 솔베이그는 $[0, 0]$과 $[1, 2]$ 중에서 고른다.

솔베이그는 트랜지스터가 가장 많은 묶음을 가져가고, 아르나르는 솔베이그가 고르고 난 뒤 자기 몫의 트랜지스터가 가장 많아지도록 구간을 정한다. 기기별 트랜지스터 개수가 주어질 때, 아르나르가 황금 트랜지스터를 갖게 될 확률을 구하라.

첫 줄에 테스트 케이스 개수 $T$가 주어진다. 이어지는 $T$개 줄에는 각각 정수 다섯 개 $N$, $p$, $q$, $r$, $s$가 주어진다. 가게에 기기가 $N$대 있고, $i$번 기기에 트랜지스터가 $((i \times p + q) \bmod r + s)$개 들어 있다는 뜻이다. 기기 번호는 0번부터 $N-1$번까지다.

• $1 \le T \le 100$
• $1 \le N \le 10^6$
• $1 \le p \le 10^6$
• $1 \le q \le 10^6$
• $1 \le r \le 10^6$
• $1 \le s \le 10^6$

테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 아르나르가 황금 트랜지스터를 갖게 될 확률이다.

y는 소수점 아래 10자리까지 출력한다. 답은 두 정수의 비이므로 소수점 아래 11번째 자리에서 반올림한다. 예를 들어 $2/3$은 0.6666666667로, $1/2$은 0.5000000000으로 출력한다.

예제 각 케이스의 기기별 트랜지스터 개수는 다음과 같다.

• 1번 케이스: 트랜지스터가 1개인 기기 한 대. 아르나르는 $[0, 0]$을 고를 수밖에 없고 솔베이그가 그 기기를 가져가므로 아르나르는 이길 수 없다.
• 2번 케이스: 2, 5, 1, 4, 7, 3, 6, 2, 5, 1. 아르나르가 $[4, 5]$를 고르면 그 구간에는 트랜지스터가 7개, 3개인 기기가 들어간다. 솔베이그는 6, 2, 5, 1개짜리가 있는 $[6, 9]$를 가져가고, 아르나르에게는 앞의 기기 여섯 대와 전체 36개 중 22개가 남는다.
• 3번 케이스: 101, 1
• 4번 케이스: 103, 120, 114, 108, 102, 119, 113, 107, 101, 118, 112, 106, 100, 117, 111, 105, 122, 116, 110, 104
• 5번 케이스: 1999999, 1999998, 1999997, 1999996, 1999995, 1999994, 1999993, 1999992, 1999991, 1999990
• 6번 케이스: 트랜지스터가 1개인 기기 두 대
• 7번 케이스: 100, 1, 2
• 8번 케이스: 기기 999999대에 모두 트랜지스터가 1999999개씩 들어 있다.