Blow up the Enemy

Problem Description

Zhang3 is playing a shooting game with Father. In the game there are two players trying to kill each other to win the game. The game provides $n$ weapons, each has two properties: Damage and Delay. The $i^\mathrm{th}$ weapon has Damage $A_i$ and Delay $D_i$. When a player shoots with this weapon, his enemy's HP is reduced by $A_i$, then he must wait for $D_i$ ms before he can shoot again. The game processes as follows:

1. Before the game starts, Zhang3 and Father choose a weapon respectively. Father always randomly chooses one of the $n$ weapons with equal probabilities. Each player can only use the chosen weapon during the game.
2. When the game starts, Zhang3 and Father have $100$ HP each. They make their first shot at the same time.
3. They keep shooting as quickly as possible. That means, a player shoots instantly whenever he can shoot, until the game ends.
4. When a player's HP is reduced to 0 or lower, he dies and the game ends. If the other player is still alive (i.e. has HP higher than 0), then the living player wins the game; otherwise (if the two players die at the same time), each player has $50\%$ probability to win the game. Zhang3 wants to win the game. Please help her to choose a weapon so that the probability to win is maximized. Print the optimal probability.

Input

The first line of the input gives the number of test cases, $T \; (1 \le T \le 100)$. $T$ test cases follow. For each test case, the first line contains an integer $n \; (1 \le n \le 1000)$, the number of weapons in the game. Then $n$ lines follow, the $i^\mathrm{th}$ of which contains two integers $A_i, D_i \; (1 \le A_i \le 100, \; 1 \le D_i \le 10000)$, representing the Damage and the Delay of each weapon. The sum of $n$ in all test cases doesn't exceed $2000$.

Output

For each test case, print a line with a real number $p \; (0 \le p \le 1)$, representing the optimal probability. Your answers should have absolute or relative errors of at most $10^{-6}$.

Sample Input

2
1
100 100
4
50 50
40 20
30 10
20 100

Sample Output

0.5
0.875

Source

2020 Multi-University Training Contest 4