I think you all know the name of Gotham city. Our hero Batman lives there. But a demon called Ra's al Ghul wants to destroy the Gotham city and Batman never let them to do so. He always try his best to protect the city and the city people.
One day Ra’s al Ghul plans to plant some bombs in Gotham city to destroy it. When our hero heard about this, he called his chief engineer Mr. Lucius Fox to find a solution. Then Mr. Lucius Fox gave him a machine, which can deactivate the bombs without any loss of individuals and the city. The machine works in a different manner. When a bomb is planted, the machine adds it in it's list and in each second the machine tries to deactivate the bomb which is present on his list and need the least time to deactivate (That means If some bombs is present in the machine’s list, the machine will spend the current second in that bomb which take less time than others to deactivate, after this current second the defuse time of this bomb will decreased by 1 second) . If two bombs need the same amount of time, the machine will try to deactivate the bomb which was planted first. When a bomb is completely deactivated, the machine deletes all the information about the bomb from its list.
Now our hero have a list which contains some information about the bombs. The list contains the bomb plant time Ti and time needed to deactivate the bomb Xi for the ith bomb. Batman wants to know average waiting time for all the bombs. (Waiting time for a bomb is the amount of time a bomb has been waiting in the machine’s list without processing)
Our hero Batman is busy with fighting with Ra's al Ghul’s people and he wants you to calculate the average waiting time for him.
Input
The first line contains a integers T (1 ≤ T ≤ 10) which indicate the test case and for each test case there is a integer in the first line N (1 ≤ N ≤ 100000), the number of bombs in in the list and following N lines contains two integer Ti (0<=Ti<=100000) and Xi (1<=Xi<=10^9) each indicating the planted time and time need to deactivate the i’th bomb. You can safely assume that all Ti is distinct. See sample input for better understanding.
Output
For each test case output a real number which is the average waiting time for each bomb.
Output four digit after the decimal point. Please see the samples for the exact formatting.
Sample
| Input | Output |
|---|---|
1 4 0 8 1 4 2 9 3 5 | Case 1: 6.5000 |
Note: The time starts from 0. In sample input for the first bomb it’s Ti value is 0 and for 2nd bomb It’s Ti value is 1. It indicate that the first bomb is planted in the 0th second and 2nd bomb is planted on the 1st second.
