P9156 "GLR-R4" Mangzhong

  "Clear clouds gently ripple, warm winds without waves, raising a cup to escape the heat as people gather." ---   "It’s the week of the Gaokao..."   There was no pressure to fight for a venue today, but no one even dared to leave the training room, because the teaching building across the way was the Gaokao exam site.   "Maybe next year we’ll be over there." Although the afternoon training was over, the cafeteria had a special schedule today, so Tianyi and A-Ling still had to cuddle in the lounge for quite a while.   "A-Ling, hungry..." As if she could not hear any topic other than food, Tianyi lay on the sofa, twirling her fingers through her hair—through A-Ling’s hair—and complaining.   "Let’s play a game." ---   **Mangzhong** "Icy soda, the restless bubbles all melt away. 　Let the lazy wind seize the chance and slip in."

  *Double Neurasthenia* is a card game that tests memory heavily. The rules are as follows.   There are $n$ different types of cards, two cards of each type. Initially, all $2n$ cards are placed face down on the table. Two players take turns. In each move, the player chooses two **different** cards and flips them up **at the same time**. These two cards are shown to both players, and then: - If the two cards are of the same type, the player gains $1$ point and takes these two cards away. The next move is still made by the **current player**. - Otherwise, the player turns these two cards face down again. The next move is made by the **other player**.   The game ends when all cards have been taken away.   Both players aim to maximize their final scores. In addition, if **both sides agree**, they may choose to draw. Suppose there are still $2n'$ cards left when they draw; then each side gets $n'/2$ points, and the game ends. To avoid the game never ending, we assume: when choosing a draw is **one of** the optimal choices for both sides, they will draw immediately. ---   Now, A-Ling and Tianyi want to play this game. Because she is too hungry, Tianyi, who is responsible for arranging the cards, accidentally placed $m$ of the $2n$ cards face up. **The types of these $m$ cards are pairwise distinct.** Both sides secretly memorized their types and positions, turned them face down again, and then started the game. We assume Tianyi and A-Ling have perfect memory and are extremely smart: they can remember the type and position of every card that has ever been shown (including the initial $m$ cards), and they will both use optimal strategies to maximize their expected scores. As the first player, A-Ling wants to know her expected score. Can you help her?   Since they really are going to cuddle in the lounge for quite a while, you need to compute the answer for $T$ test cases of $(n,m)$.

The first line contains an integer $T$, the number of test cases. The next $T$ lines each contain two integers $n,m$, representing the number of card types in this game and the number of cards that were flipped up in advance and then turned face down again.

Output $T$ lines. Each line contains one real number, the answer for that test case. Your output is considered correct if and only if the relative error or absolute error compared with the standard answer does not exceed $10^{-6}$.

#### Explanation for Sample #1 For the first test case, the pair of cards flipped by the first player must be of the same type, so they take them away and the game ends. The first player’s expected score is $1$. For the third test case, it can be proven that both sides will agree to draw at the start of the game. The expected scores of the first and second players are both $1$. ### Constraints For $100\%$ of the data, $1\le n\le 5\times10^3$, $0\le m\le n$. For different subtasks, the constraints are as follows: | Subtask ID | $n,m$ | $T$ | Special Property | Score | | :--------: | :--------------: | :--------------: | :--------------: | :---: | | $1$ | $\le2$ | $\le5$ | None | $10$ | | $2$ | $\le8$ | $\le44$ | None | $20$ | | $3$ | $\le5\times10^3$ | $\le5\times10^3$ | Yes | $10$ | | $4$ | $\le5\times10^3$ | $=1$ | None | $20$ | | $5$ | $\le5\times10^3$ | $\le5\times10^3$ | None | $40$ | - Special Property: $n=m$. Translated by ChatGPT 5