Aris 正在玩经典游戏《愤怒的小鸟》（Angry Birds）！

因为 Aris 玩得太久了，优香（Yuuka）没收了 Aris 的游戏机，并要求 Aris 在拿回游戏机之前完成今天的数学作业。

然而，老师（Sensei）今天并没有给 Aris 布置任何数学作业，所以优香不得不自己出一道题让 Aris 来解决。

将《愤怒的小鸟》的游戏场地视为三维欧几里得空间，并将小鸟视为一个半径为 $R_3$ 的球体。建立空间直角坐标系 $O - xyz$，使得小鸟中心的运动轨迹位于水平面 $z = 0$ 上。

已知小鸟中心的轨迹是一条闭合折线，由首尾相连的 $n$ 条线段组成。连接点为 $n$ 个点：$(x_1, y_1, 0), (x_2, y_2, 0), \dots, (x_n, y_n, 0)$。第 $i$ 条线段的端点为 $(x_i, y_i, 0)$ 和 $(x_{i \bmod n + 1}, y_{i \bmod n + 1}, 0)$。然而，由于传感器误差，实际的 $n$ 个点可能会偏离 $(x_i, y_i, 0)$，偏差距离不超过 $R_2$（所有点的传感器偏差 $R_2$ 均相同）。也就是说，实际的第 $i$ 个点 $(x'_i, y'_i, 0)$ 可以是平面 $z = 0$ 内以 $(x_i, y_i, 0)$ 为圆心、半径为 $R_2$ 的圆盘（该圆盘仍包含在平面 $z = 0$ 中）内的任意位置。

设 $S$ 为整只小鸟可能经过的所有点的集合，即三维空间中到小鸟中心轨迹的距离最大为 $R_3$ 的点集。优香要求 Aris 计算 $S$ 的凸包的体积。

凸包：点集 $S$ 的凸包定义为最小的集合 $T$，使得对于 $S$ 中的任意两点，它们之间线段上的所有点也都包含在 $T$ 中。

输入格式

第一行包含一个正整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。

对于每个测试用例：

第一行包含三个整数 $n, R_2, R_3$ ($1 \le n \le 10^5$, $0 \le R_2, R_3 \le 10^6$)，分别表示连接点的数量、传感器误差半径和小鸟的半径。

接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$ ($|x_i|, |y_i| \le 10^6$)，表示轨迹的第 $i$ 个连接点。

保证所有测试用例中 $n$ 的总和在单个测试点内不超过 $10^5$。

输出格式

对于每个测试用例，输出一个浮点数，表示答案。如果你的答案与标准答案的相对误差或绝对误差不超过 $10^{-9}$，则视为正确。

设你的答案为 $a$，标准答案为 $b$。如果 $\frac{|a-b|}{\max\{b,1\}} \le 10^{-9}$，则视为正确。

样例

输入样例 1

1
5 1 1
0 0
3 1
2 3
2 2
-1 3

输出样例 1

77.622211120429589

说明

小鸟中心可能经过的所有点集的凸包：

小鸟中心可能经过的所有点集的凸包