God! Save me

You are in a room with $n$ doors. If you open the door numbered $i$, then after $x_i$ hours you will either reach a safe place or return to this same room. Calculate the expected time $P$ (in hours) after which you can escape the room to a safe place.

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 following $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 represents the time after which you can reach a safe place;

• If $x_i$ is negative, then $|x_i|$ represents the time after which you will find yourself back in 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 from the room;

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

Examples