eolymp
bolt
Try our new interface for solving problems
Problems

God! Save me

God! Save me

Time limit 1 second
Memory limit 128 MiB

You are located in a room with n doors. If you open the i-th door, in x_i hours you will be either get to a safe place or you will return to the same room again. What is the expected time P (in hours) until you can move to the safe place?

Input data

The first line is the number of test cases. The first line of each test case contains the value of 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 indicates the time in which you will get to a safe place;

  • if x_i is negative, then | x_i | indicates the time in which you will return to the room;

The value of p_i is the probability to open the i-th door. The sum of all p_i equals 1.

Output data

For each test case, first print the serial number of the case, a colon, a space and then print “God! Save me” (without the quotes) if you can't expect to be in the safe place, otherwise print the value of P with 6 digits after the decimal point.

Examples

Input example #1
3
3
2 0.33
-3 0.33
-5 0.34
3
2 0.34
-3 0.33
-5 0.33
3
10 0.0
-1 0.4
-1 0.6
Output example #1
Case 1: 10.151515
Case 2: 9.764706
Case 3: God! Save me