To be frank with you, this problem is a classic problem of tremendous magnitude which may increase the difficulty of this problem.
We define a type of operation concerning a positive integer $n$ $(n > 1)$ as to replace it with an integer $d$, one of factors of $n$ $(1 \leq d \leq n)$.
You are given a positive integer $n$ and then we will ask you to determine the expectation number of times to utilize this type of operation if we want to change $n$ into $1$ by operating again and again, assuming each possible $d$ in each operation has equal possibility to select.
For the sake of calculation, $n$ and all its distinct prime factors $p_1, p_2, \cdots, p_m$ will be given, satisfying $n$ has $m$ distinct prime factors exactly.
Input
The input contains multiple test cases.
For each test case:
The first line contains two positive integers $n$ and $m$ which indicates $m$ is the number of distinct prime factors of $n$, satisfying $2 \leq n \leq 10^{24}$.
The second lines contains $m$ distinct prime numbers $p_1, p_2, \cdots, p_m$, satisfying $2 \leq p_i \leq 10^6$.
About $2 \cdot 10^5$ test cases in total.
Warm Tips for C/C++:
__int128_t is available here but standard solutions of this problem do not use this compiler-dependent data type.
Output
For each test case, output "
Case #$x$: $y$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y$ denotes the expectation number of times to utilize this type of operation of corresponding case. Your answer will be considered correct if its absolute or relative error won't exceed $10^{-9}$.
SampleInput
2 1
2
4 1
2
6 2
2 3
8 1
2
10 2
2 5
12 2
2 3
SampleOutput
Case #1: 2.0000000000
Case #2: 2.5000000000
Case #3: 2.6666666667
Case #4: 2.8333333333
Case #5: 2.6666666667
Case #6: 3.0333333333