Mr Hu was recently hooked on a game called "Flipping cards".
There are \(2n\) cards on the desk. Each card has a positive integer on its front side, and initially all cards are placed with the back side up (so initially Mr Hu cannot see the integer of each card). Each positive integer from \(1\) to \(n\) appears on exactly two cards.
In each operation, Mr Hu will choose two cards and flip them to see the two integers. If the two integers equal to each other, Mr Hu will eliminate them. Otherwise, they will be flipped back. Notice that Mr Hu must have chosen the two cards before flipping the two cards simultaneously.
Mr Hu has a great memory, so he can remember all the integers of the cards which used to be flipped. Now, he wants to know what is the expect number of operations for him to eliminating all the cards.
The first line contains an integer \(T(1\leq T\leq 20000)\), representing the number of test cases.
Then \(T\) line follows. Each line contains a positive integer \(n(1\leq n\leq 5000)\), representing the maximum integers on the cards (so there are \(2n\) cards).
Output \(T\) lines.
For each test case, output a floating number in a line, representing the expect number of operations. The answer should be rounded to two digits after the decimal point.
The following is the best strategy when \(n=2\):
(1) Randomly choose two cards. There is a \(\frac{1}{3}\) probability to flip two cards with the same integers, in which case we eliminate them and skip to step (4). Otherwise skip to step (2).
(2) Choose a card which used to be flipped, and another which has not been flipped. There is a \(\frac{1}{2}\) probability to flip two cards with the same integers, in which case we eliminate them and skip to step (4). Otherwise skip to step (3).
(3) Now we have known the integer of each card. We choose a pair and eliminate them.
(4) We eliminate the last two cards.
The expect number of operations is \(E=\frac{1}{3}\times 2 + (1-\frac{1}{3})(\frac{1}{2}\times 3+(1-\frac{1}{2})\times 4)=3.00\).