Deceitful War (Large)

Naomi and Ken sometimes play games together. Before they play, each of them gets N identical-looking blocks of wood with masses between 0.0kg and 1.0kg, exclusive. All of the blocks have different masses. There are lots of games they could play with those blocks, but they usually play something they call War. Here is how War works.

1. Each player weighs each of his or her own blocks, so each player knows the masses of all of his or her own blocks, but not the masses of the other player's blocks.
2. They repeat the following process N times.
   1. Naomi chooses one of her own blocks, with mass ChosenNaomi.
   2. Naomi tells Ken the mass of the block she chose.
   3. Ken chooses one of his own blocks, with mass ChosenKen.
   4. They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
   5. Both blocks are destroyed in a fire.

Naomi has realized three things about War. First, she has realized that she loses a lot. Second, she has realized that there is a unique strategy Ken can follow to maximize his points without assuming anything about Naomi's strategy, and that Ken always uses it. Third, she has realized that she hates to lose. Naomi has decided that instead of playing War, she will play a game she calls Deceitful War. The great thing about Deceitful War is that Ken will think they are playing War.

Here is how Deceitful War works, with the differences from War in bold.

1. Each player weighs each of his or her own blocks. Naomi also weighs Ken's blocks while he is not looking, so Naomi knows the masses of all blocks. Ken only knows the masses of his own blocks.
2. They repeat the following process N times.
   1. Naomi chooses one of her own blocks, with mass ChosenNaomi.
   2. Naomi tells Ken a number ToldNaomi, between 0.0kg and 1.0kg exclusive. Ken, who thinks they are playing War, thinks the number Naomi just told him is ChosenNaomi.
   3. Ken chooses one of his own blocks, with mass ChosenKen.
   4. They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
   5. Both blocks are destroyed in a fire.

Naomi does not want Ken to know that she is not playing War, so when she is choosing which block to play and what mass to tell Ken, she must make sure that the balance scale will not reveal that ChosenNaomi differs from ToldNaomi. In other words, she must make decisions so that:

• ChosenNaomi > ChosenKen if, and only if, ToldNaomi > ChosenKen, and
• ToldNaomi is not equal to the mass of any of Ken's blocks, because he knows that is not possible.

It might seem like Naomi will not win any extra points by being deceitful, because Ken might discover that she was not playing War. But Naomi knows Ken thinks both players are playing War, and she knows what he knows, and she knows Ken will always follow his unique optimal strategy for War, so she can always predict what he will play.

You are given the masses of the blocks Naomi and Ken started with. Naomi plays Deceitful War optimally to gain the maximum number of points. Ken plays War optimally to gain the maximum number of points, assuming that both players are playing War. What will Naomi's score be? What would it have been if she had played War optimally instead?

How the rules play out

If each player has a single block left, where Naomi has 0.5kg and Ken has 0.6kg, then Ken is guaranteed to score the point. Naomi cannot say her number is 0.6kg or more, or Ken will know she is not playing War when the balance scale shows his block was heavier.

If each player has two blocks left, where Naomi has 0.7kg and 0.2kg and Ken has 0.8kg and 0.3kg, then Naomi could choose her 0.2kg block and deceive Ken by telling him that she chose a block that was 0.6kg. Ken assumes Naomi is telling the truth, as the rules of War say, and plays his 0.8kg block to score a point. Ken was just deceived, but he will never realize it, because the balance scale shows that his 0.8kg block is heavier, exactly as he expected. Now Naomi can play her 0.7kg block, tell Ken it is 0.7kg, and score a point. If Naomi had played War instead of Deceitful War, then Ken would have scored two points and Naomi would have scored zero.

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer N, the number of blocks each player has. The next line contains N space separated real numbers: the masses of Naomi's blocks, in kg. The last line contains N space separated real numbers: the masses of Ken's blocks, in kg.

Each of the masses given to Ken and Naomi is written as a 0, followed by a decimal point, followed by 1 to 5 digits. Even though every number in the input has 1 to 5 digits after the decimal point, Ken and Naomi do not know that, so Naomi can still tell Ken that she played a block with mass 0.5000001kg, and Ken has no reason not to believe her.

Limits

• $1 \le T \le 50$
• $1 \le N \le 1000$
• All the masses given to Ken and Naomi are distinct, and between 0.0 and 1.0 exclusive.

For each test case, output one line containing "Case #x: y z", where x is the test case number starting from 1, y is the number of points Naomi will score if she plays Deceitful War optimally, and z is the number of points Naomi will score if she plays War optimally.