Bob 收集了许多不同种类的硬币。他想知道哪种硬币是幸运的。他通过以下方式找出幸运的硬币种类：他同时抛掷所有硬币，然后移去所有反面朝上的硬币。接着，他抛掷所有剩余的硬币，并移去反面朝上的硬币。他重复上述步骤，直到只剩下一类硬币，或者没有硬币剩下。如果最后只剩下一类硬币，那么这一类硬币就是幸运的。给定每种硬币的数量以及抛掷时正面朝上的概率，你的任务是计算每种硬币成为幸运硬币的概率。

输入格式

第一行是测试用例的数量。对于每个测试用例，第一行包含一个整数 $k$，表示硬币的种类数。接下来的 $k$ 行中，每行描述一种硬币，包含一个整数和一个实数，分别表示该种硬币的数量以及抛掷时正面朝上的概率。保证硬币种类数不超过 $10$，硬币总数不超过 $1000000$，且抛掷时正面朝上的概率在 $0.4$ 到 $0.6$ 之间。

输出格式

对于每个测试用例，输出一行，包含 $k$ 个实数（保留 6 位小数），分别表示每种硬币成为幸运硬币的概率。

样例

输入样例 1

3
1
1000000 0.5
2
1 0.4
1 0.6
3
2 0.4
2 0.5
2 0.6

输出样例 1

1.000000
0.210526 0.473684
0.124867 0.234823 0.420066