Expectation Division

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.

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.

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}$.

2 1
2
4 1
2
6 2
2 3
8 1
2
10 2
2 5
12 2
2 3

Case #1: 2.0000000000
Case #2: 2.5000000000
Case #3: 2.6666666667
Case #4: 2.8333333333
Case #5: 2.6666666667
Case #6: 3.0333333333

2017 Multi-University Training Contest - Team 1