It's said that Aladdin had to solve seven mysteries before getting the Magical Lamp which summons a powerful Genie. Here we are concerned about the second mystery.

Aladdin was going along a magical cave, tricked by the evil sorcerer, searching for the great Magical Lamp. Then he found a strange Lamp, thinking that it might be the lamp the sorcerer had spoken off, rubbed it and a Genie appeared. But alas! He was unlucky as the lamp was owned by an evil Genie. It blindfolded Aladdin and gave him a task to finish. Aladdin finished that task and moved forward.

The task was that, there were n sticks, each had a particular weight. Two types of sticks were there, one kind of sticks had distinguishable rough patterns that can be identified by just touching. Other types of sticks were indistinguishable. Each time Aladdin had to pick a stick from all sticks and put it into a magical box. If all the sticks are put into the box at least once, Aladdin will be free; otherwise the stick he just put will be put with the other sticks.

So, Aladdin planned that each time he will pick a new stick randomly and put it into the magical box. So, once he put a distinguishable stick into the box, he will not put it again though it's mixed with other sticks, since he can remember the roughness of every distinguishable stick. But for indistinguishable sticks he had no option. So, each time he put a stick that looked new to him, but that might not be a new one. And each time the probability of picking a new (to Aladdin of course!) stick is equal. Now your task is to find the expected summation of weights of sticks Aladdin had to put into the box before he was free.

For example, let's say there were two sticks, one was distinguishable and the other one was indistinguishable. And the weights were 4, 8 respectively. Let's calculate the expected summation of weights of sticks.

1. Aladdin puts stick 1 (weight 4). The probability is 1/2. As all the sticks are not put into the box at least once, so, it will be put with the other stick again. Aladdin will not put stick 1 again, since he can distinguish it from others. So, he puts stick 2 next. And since all the sticks are put in the box at least once, so he is free. Total weight he put is 4 + 8 = 12. So, the expected summation of weights is (1/2) * 12 = 6.
2. Let's say he puts stick 2 (weight 8). The probability is 1/2. Now it will be put back with the other stick. So, Aladdin has two sticks again, where he is not sure which one he had put into the box, as he cannot distinguish stick 2. So, he kept trying stick 1 and 2. And if he puts stick 2 again, he faces the same situation, but if he puts stick 1, he is free as all the sticks are put into the box at least once. Let's say the expected summation of weights of sticks from this situation is x. If he puts stick 1 (weight 4, but probability is 1/2), he is free. If he puts stick 2 (weight 8), he is in the same situation. So, x = (1/2) * 4 + (1/2) * (x + 8). So, x = 12. So, the expected summation of weights is (1/2) * (8 + 12) = 10.

So, from the both outcomes, the final result is 6 + 10 = 16.

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 5000). Each of the next n lines contains two integers a_i b_i (1 ≤ a_i ≤ 5000, 1 ≤ b_i ≤ 2) where a_i denotes the length of the stick and b_i denotes the type. b_i = 1 indicates that the stick is distinguishable from others, b_i = 2 means it is not distinguishable.

For each case, print the case number and the expected summation of weights of the sticks Aladdin had to put into the box. Errors less than 10^-4 will be ignored.