题目描述

朱哥带来了 $(n)$ 个外形相同的密封箱子，其中恰有 1 个箱子含有有毒气体，其余 $(n-1)$ 个箱子安全。小方与小谢决定玩一个检测游戏来决定奖品归属。

两人轮流行动，小方先手。在每一回合中，当前玩家必须从场上尚未被移除的箱子中选择 1 个 进行检测。检测仪器的准确率为$(p)$ ，满足 $(0.5 < p < 1)$。每次检测结果独立生成，且公开给双方。 检测规则如下（单次检测）：

• 若被测箱子真实为安全：以概率 $(p)$ 返回 “SAFE”，以概率 $(1-p)$ 返回 “TOXIC”；
• 若被测箱子真实为有毒：以概率 $(p)$ 返回 “TOXIC”，以概率 $(1-p)$ 返回 “SAFE”。

检测结果揭晓后，按下述规则执行：

1. 若结果为 “TOXIC”：该箱子立即移除（不揭示其真实属性），回合结束，轮到对方行动；
2. 若结果为 “SAFE”：当前玩家必须立刻二选一：
   • 打开该箱子：若该箱真实安全，则当前玩家立即获胜；若真实有毒，则当前玩家立即失败（对方获胜）；
   • 不打开：该箱子立即移除（不揭示其真实属性），回合结束，轮到对方行动。

游戏在以下任意情况发生时立即结束。

• 打开箱子将立刻揭示真实状态并结束游戏：开安全者胜；开有毒者负。
• 当场上只剩 1 个箱子时：轮到行动的玩家必须直接打开该箱子（不再进行检测）；若安全则该玩家获胜，若有毒则该玩家失败。

朱哥给了小方一次 “二次检测权” ，可在她的任意一次回合中使用一次（也可选择不用）。 当小方在自己的回合选择某个箱子并声明使用特权时：

• 对该箱子进行两次独立检测（两次均满足上述准确率 $(p)$ ，结果独立且公开）；
• 若两次检测中至少有一次为 “TOXIC”：则该箱子立即移除，回合结束，轮到对方行动；
• 若两次检测结果均为 “SAFE”：小方可立即选择打开该箱或不打开：
  • 打开：若真实安全则小方立即获胜；若真实有毒则小方立即失败；
  • 不打开：该箱子立即移除，回合结束，轮到对方行动。

该特权只能使用一次。

假设两名玩家都采取最优策略（均尽力最大化自身胜率），请计算：

小方在游戏开始时的最大获胜概率。

输入格式

• 第一行包含一个整数 $T$，表示测试用例的数量。
• 接下来 $T$ 行，每行包含两个数 $n_i$ $p_i$。
  • $n_i$为整数，代表箱子数量；
  • $p_i$为实数，代表检测准确率，满足 $(0.5 < p_i < 1)$。

输出格式

对每组数据，输出一个实数，表示小方在最优策略下的最大获胜概率。 当你的答案与标准答案的绝对或相对误差不超过 $(10^{-12})$时，视为正确。

样例

样例输入

2
3 0.6
5 0.7

样例输出

0.400000000000
0.659433333333

数据范围

• $(1 \le T \le 10^5)$
• $(2 \le n \le 10^6)$
• $(0.5 < p < 1)$
• 所有测试的总规模不超过 $(10^6)$ 。