Double Memory Game

Problem Statement:

A card‐matching game named Double Memory Game is played by two players. Initially there are n pairs of cards (i.e. 2n cards), where each type appears exactly twice. All cards are placed face‐down on the table.

However, before the game begins, due to a mishap, m cards are accidentally placed face–up. These m cards are all of distinct types (i.e. no two of them form a pair). Both players secretly memorize the positions and types of these cards; then the cards are turned face–down again and the game starts.

The players take turns. In each move the current player selects two different cards and turns them up simultaneously. The cards are revealed to both players. Then:

• If the two cards are of the same type, the mover scores 1 point and removes these two cards from the table. The same player then makes the next move.
• If they are not the same, the cards are turned face–down again and the turn passes to the opponent.

The game continues until all cards have been removed. Both players wish to maximize their final score. Moreover, if at some point both players agree, they can choose to draw. Suppose that at the moment of draw there are 2n' cards remaining; then each player receives n'/2 points and the game ends. (To avoid the possibility of an endless game we assume that if choosing a draw is among the optimal choices for both players, they will agree to it immediately.)

Both players are assumed to have perfect memory (remembering all cards that have ever been revealed, including the initial m face–up cards) and are extremely clever. The first–move player (named Aly) would like to know her expected final score if both play optimally.

You are given T test cases. For each test case, given the values of n and m (m cards were initially momentarily face–up, each of distinct type), compute the expected score of the first player.

Game Analysis and Modeling:

After the initial reveal, note that for each revealed card, its mate (of the same type) is still unknown. Thus, the board can be described by two numbers:

• a: the number of pairs for which one card is known (these come from the initially revealed cards or later moves) – these are called half–known pairs.
• b: the number of pairs that are completely unknown.

Initially we have a = m and b = n – m. Let f(a, b) be the game value (i.e. the difference in the final scores from the viewpoint of the current player) when the board is in state (a, b) and it is that player’s turn. Then the final score of the current player will be

$$S = \frac{f(a,b) + (a+b)}{2}.$$

The move available to a player depends on the state:

• Option 1: If a > 0, choose one known card (from a half–known pair) and one unknown card. When doing so, with probability \(1/(a+2b)\) the unknown card is the matching card (so the player gains 1 point and the state becomes (a-1, b) with an extra move), and with probability \((a+2b-1)/(a+2b)\) it is not. In the latter case the revealed card is from either:
• a half–known pair (other than the chosen one), in which case that pair becomes complete and is immediately claimed by the opponent (the outcome is –(1 + f(a-1,b))), or
• a completely unknown pair, in which case that pair becomes half–known and the turn passes (yielding –f(a+1,b-1)).
• Option 2: Pick two unknown cards. Among the \(a+2b\) unknown cards, if the two form a matching pair (which can occur only if they come from a completely unknown pair) then the player scores immediately and the state becomes (a, b-1) with an extra move. Otherwise, two cards are revealed. There are several subcases (depending on whether each card comes from a half–known or a totally unknown pair), each yielding immediate opponent scores or state updates with the turn switching.

After computing the expected game value f(a,b) through a proper dynamic programming recurrence (taking the maximum over the available moves), the answer for a test case with parameters n and m is given by evaluating

$$\text{answer} = \frac{f(m,n-m) + n}{2}.$$

Your task is to implement this computation. It is guaranteed that under optimal play both players will force the game to an end.

inputFormat

The first line contains an integer T, the number of test cases. Each of the next T lines contains two integers n and m, where 1 ≤ n and 0 ≤ m ≤ n.

outputFormat

For each test case, output a single line containing the expected score of the first player. Answers within an absolute or relative error of 10^-6 will be accepted.

sample

4
1 0
1 1
2 0
2 1

1.000000
1.000000
1.333333
1.333333

</p>