God! Save me

Input

The first line contains the number of tests.

The first line of each test contains the number of doors $n$ (0 < n < 100).

Each of the next $n$ lines contains two numbers: x_i (0 < |x_i| < 25) and p_i (0 \le p_i \le 1).

• If x_i is positive, it is the time after which you reach a safe place.

• If x_i is negative, |x_i| is the time after which you return to the room.

Here, p_i is the probability of opening the $i$-th door. The sum of all p_i equals $1$.

Output

For each test, print its number, a colon, a space, and then:

• the phrase God! Save me if it is impossible to escape the room,

• or the expected time $P$, to $6$ decimal places, after which you can escape the room to a safe place.

Examples