Expectation Division

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

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

Sample Input

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

Sample Output

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

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码