Docriz 老师正计划从班里挑选一些学生参加打字比赛。

班里共有 $n$ 名学生。第 $i$ 位同学的初始打字速度为 $s_i$，打字噪音为 $f_i$。然而，当多名学生被选中参赛时，他们的总打字速度并不是每个人初始打字速度之和，因为每个人产生的噪音会影响其他人。

具体来说，如果学生 $1, 2, 3, \dots, k$ 组成一个团队，那么学生 $1$ 的实际打字速度为 $s_1 \cdot (1 - f_1f_2 - f_1f_3 - \dots - f_1f_k)$，学生 $2$ 的实际打字速度为 $s_2 \cdot (1 - f_2f_1 - f_2f_3 - \dots - f_2f_k)$，以此类推。

Docriz 老师想要组建一个团队，使得总打字速度尽可能大。请帮他计算他所能达到的最大总打字速度。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2000$)，表示测试用例的数量。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 100$)，表示学生人数。 接下来 $n$ 行，每行包含两个数字 $s_i, f_i$ ($1 \le s_i \le 10^{12}, 0 \le f_i \le 1$)，其中 $s_i$ 是整数，$f_i$ 是一个恰好有两位小数的实数。

保证 $\sum n \le 2000$。

输出格式

对于每个测试用例，输出一行，包含一个实数：Docriz 老师能达到的最大总打字速度。请将答案保留小数点后恰好 $9$ 位。

保证答案在保留 $9$ 位小数时是绝对精确的，因此只有与标准答案完全一致的输出才会被接受，请务必确保输出的精度。

样例

输入 1

4
3
10 0.00
11 0.00
12 0.00
3
10 1.00
11 1.00
12 1.00
3
10 0.50
11 0.50
12 0.50
3
10 0.33
11 0.21
12 0.92

输出 1

33.000000000
12.000000000
17.250000000
20.421900000