Description

有人认为哄婴儿入睡是一门艺术，但这个问题将证明它其实只是数学。

考虑一个夜晚，父母正试图哄婴儿入睡。闹钟会在夜晚结束时响起，父母不能更改闹钟时间，因此夜晚的时长固定为从现在开始的 $k$ 小时。

婴儿可能处于以下三种状态之一：

• 状态 0 表示婴儿醒着；
• 状态 1 表示婴儿处于浅睡眠；
• 状态 2 表示婴儿处于深睡眠。

婴儿初始状态为 0，状态变化是连续而非离散的。给定三个概率值 $p_0$、$p_1$ 和 $p_2$。当婴儿处于状态 $i$ 时，接下来的 $x$ 小时内不发生状态变化的概率为 $p_i^x$（$x$ 为正实数）。换句话说，下一次状态变化的时间服从指数分布，其累积分布函数为 $1 - p_i^x$。

当状态变化发生时：

• 如果婴儿当前处于状态 0，则必定转移到状态 1；
• 如果处于状态 2，也必定转移到状态 1；
• 如果处于状态 1，则以概率 $q_0$ 转移到状态 0，以概率 $1 - q_0$ 转移到状态 2。

父母可以自行决定何时入睡，但只有婴儿处于状态 1 或 2 时才能入睡（状态 0 时婴儿会哭闹吵醒父母）。即使婴儿处于可入睡状态，父母也可以选择保持清醒。若保持清醒，父母可以：

1. 观察婴儿当前状态；
2. 阻止婴儿醒来：如果婴儿根据规则本应从状态 1 转移到状态 0，而父母未入睡，则婴儿会被安抚并保持在状态 1。

父母可以根据婴儿当前状态或时间等因素自由决定何时入睡。一旦入睡，将持续睡眠直到：

• 婴儿醒来（进入状态 0），或
• 闹钟在 $k$ 小时结束时响起。

若被婴儿吵醒，父母可以再次选择入睡时机。

问题：在最优策略下，父母能获得的最大期望睡眠时长是多少？

Input Format

第一行输入整数 $t$（$1 \le t \le 1000$）——测试用例数量。
接下来 $t$ 行，每行包含 5 个精确到小数点后一位的浮点数，依次为：$k$、$p_0$、$p_1$、$p_2$、$q_0$（$0.1 \le k \le 10$；$0.1 \le p_0, p_1, p_2, q_0 \le 0.9$）。

Output Format

输出 $t$ 行，每行一个浮点数表示对应测试用例的最大期望睡眠时长。答案与标准解的绝对误差不超过 $10^{-9}$ 即视为正确。

2
10.0 0.5 0.5 0.5 0.5
8.0 0.1 0.9 0.9 0.1

6.5990202123649855
7.540407031059442

Hint

翻译由 DeepSeek V3 完成