#216763. [GKS 2020 #D] Beauty of tree

Amadea and Bilva are decorating a rooted tree containing nodes, labelled from 1 to . Node 1 is the root of the tree, and all other nodes have a node with a numerically smaller label as their parent.

Amadea and Bilva's decorate the tree as follows:

• Amadea picks a node of the tree uniformly at random and paints it. Then, she travels up the tree painting every -th node until she reaches the root.
• Bilva picks a node of the tree uniformly at random and paints it. Then, she travels up the tree painting every -th node until she reaches the root.

The beauty of the tree is equal to the number of nodes painted at least once by either Amadea or Bilva. Note that even if they both paint a node, it only counts once.

What is the expected beauty of the tree?

The first line of the input gives the number of test cases, . test cases follow. Each test case begins with a line containing the three integers , and . The second line contains integers. The i-th integer is the parent of node .

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the expected beauty of the tree.

y will be considered correct if it is within an absolute or relative error of of the correct answer.

样例输入 1

3
8 2 3
1 1 3 4 4 3 4
10 3 4
1 1 1 1 1 1 1 1 1
4 3 1
1 2 3

样例输出 1

Case #1: 2.65625
Case #2: 1.9
Case #3: 2.875

Limits

.

.

.

Test Set 1

.

Test Set 2

For up to 5 cases, .

For all other cases, .