题目描述

Amadea and Bilva are decorating a rooted tree containing $N$ nodes, labelled from 1 to $N$. 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 ${A}$-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 ${B}$-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, $T$. $T$ test cases follow. Each test case begins with a line containing the three integers $N$, $A$ and $B$. The second line contains $N-1$ integers. The i-th integer is the parent of node $i+1$.

输出格式

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 $10^{-6}$ of the correct answer.

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

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

提示

Limits

$1 \le T \le 100$.

$1 \le A \le N$.

$1 \le B \le N$.

Test Set 1

$1 \le N \le 100$.

Test Set 2

For up to 5 cases, $1 \le N \le 5 \times 10^5$.

For all other cases, $1 \le N \le 100$.