Expectation Division

Problem 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≤d≤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 p1,p2,?,pm 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≤n≤1024.

The second lines contains m distinct prime numbers p1,p2,?,pm, satisfying 2≤pi≤106.

About 2⋅105 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

 

Sample Output