Magical, Marvelous Tour

The owner of an electronics factory hid a golden transistor inside seven of her devices. Whoever buys one of those devices is invited to tour the factory.

Arnar and Solveig heard that exactly one device in their local store holds a golden transistor. They pooled their money, bought every device in the store, lined the devices up and numbered them $0$ to $N-1$. Each device holds some number of transistors. Then they agreed on a rule for deciding who keeps the golden transistor.

Arnar first picks a range $[a, b]$, both ends included, with $0 \le a \le b < N$. Solveig then picks one group of devices to take.

• If $a > 0$, she may take every device in $[0, a-1]$.
• If $b < N-1$, she may take every device in $[b+1, N-1]$.
• She may always take every device in $[a, b]$.

Once Solveig has picked a group, Arnar keeps every device she did not take.

For example, with three devices and Arnar picking $[1, 1]$, Solveig picks one of $[0, 0]$, $[1, 1]$ and $[2, 2]$. If Arnar picks $[1, 2]$, Solveig picks either $[0, 0]$ or $[1, 2]$.

The golden transistor is equally likely to be any one of the transistors, so a person's chance of touring the factory is the number of transistors that person keeps divided by the total number of transistors. Both of them pick so that their own chance is as large as possible. Find Arnar's chance of touring the factory.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains five integers $N$, $p$, $q$, $r$ and $s$. There are $N$ devices, and device $i$ holds $((i \times p + q) \bmod r) + s$ transistors. The devices are numbered $0$ to $N-1$.

Constraints:

• $1 \le T \le 100$
• $1 \le N \le 10^6$
• $1 \le p, q, r, s \le 10^6$
• The sum of $N$ over all test cases is at most $2 \times 10^6$.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is Arnar's chance of touring the factory. Print $y$ with exactly 10 digits after the decimal point, rounding the 11th digit half up.