史高治·麦克达克（Scrooge McDuck）得到了一个古老的玛雅鸭（Mayaduck）迷宫的地图，里面装满了黄金和其他宝藏。他知道迷宫中恰好有 $N$ 个房间，他希望访问所有的房间以带走所有的财富。每个房间恰好有一个出口通往另一个房间。每个房间最多有一个入口来自另一个房间。主要的问题是，迷宫与外部空间之间没有通道，且某些房间对之间也没有通道。史高治决定使用“鸭子传送公司”（Duck Teleportation Company）的设备来解决这个问题。他可以传送到迷宫内的任何房间，也可以传送到迷宫外。但还有一个问题：每次传送（跳转）都需要花费巨额资金，麦克达克需要最小化传送的次数。

在史高治的地图上，房间被编号为 $1$ 到 $N$，并且在每个房间里都写着一个可以前往的房间编号。不幸的是，由于年代久远，一些编号已经损坏且无法辨认。

假设史高治的策略是最佳的，且所有可能的迷宫结构都是等概率的，你需要求出史高治探索所有房间并返回迷宫外部所需的期望花费。他的旅程从迷宫外部开始。

输入格式

输入的第一行包含一个整数 $T$（$0 < T \le 100$），表示测试用例的总数。

每个测试用例由两行描述。

第一行包含两个整数：房间数量 $1 < N \le 4000$ 和单次传送的花费 $0 \le c \le 1000$。

第二行包含 $N$ 个整数 $0 \le a_i \le N$，表示从第 $i$ 个房间可以直接前往的房间编号。如果某个房间的编号无法辨认，则 $a_i = 0$。

所有测试用例之间用一个空行隔开。所有测试用例中 $N$ 的总和不超过 $4000$。保证所有输入数据都是合法的，即至少存在一种与输入数据相符的迷宫结构。

输出格式

对于每个测试用例，在一行中输出一个浮点数，表示该问题的答案，要求绝对误差或相对误差不超过 $10^{-6}$。

样例

输入格式 1

3
2 1
0 0

3 2
2 3 1

4 1
0 0 0 0

输出格式 1

1.000000
2.000000
1.333333