{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"It\u0027s 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.\n\nAladdin 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.\n\nThe 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.\n\nSo, 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\u0027s 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](http://en.wikipedia.org/wiki/Expected_value) summation of weights of sticks Aladdin had to put into the box before he was free.\n\nFor example, let\u0027s say there were two sticks, one was distinguishable and the other one was indistinguishable. And the weights were 4, 8 respectively. Let\u0027s calculate the expected summation of weights of sticks.\n\n1. 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 \u003d 12. So, the expected summation of weights is (1/2) * 12 \u003d 6.\n2. Let\u0027s 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\u0027s 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 \u003d (1/2) * 4 + (1/2) * (x + 8). So, x \u003d 12. So, the expected summation of weights is (1/2) * (8 + 12) \u003d 10.\n\nSo, from the both outcomes, the final result is 6 + 10 \u003d 16."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 10)**, denoting the number of test cases.\n\nEach case starts with a line containing an integer **n (1 \u0026le; n \u0026le; 5000)**. Each of the next **n** lines contains two integers **a\u003csub\u003ei\u003c/sub\u003e b\u003csub\u003ei\u003c/sub\u003e (1 \u0026le; a\u003csub\u003ei\u003c/sub\u003e \u0026le; 5000, 1 \u0026le; b\u003csub\u003ei\u003c/sub\u003e \u0026le; 2)** where **a\u003csub\u003ei\u003c/sub\u003e** denotes the length of the stick and **b\u003csub\u003ei\u003c/sub\u003e** denotes the type. **b\u003csub\u003ei\u003c/sub\u003e** **\u003d 1** indicates that the stick is distinguishable from others, **b\u003csub\u003ei\u003c/sub\u003e \u003d 2** means it is not distinguishable."}},{"title":"Output","value":{"format":"MD","content":"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\u003csup\u003e-4\u003c/sup\u003e** will be ignored."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n2\n4 1\n8 2\n2\n5 1\n6 1\n2\n2 2\n5 2\n3\n1 1\n2 2\n5 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 16\nCase 2: 11\nCase 3: 10.5000000000\nCase 4: 13.8333333333\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}