You are enjoying a lovely weekend afternoon in a new amusement park. The park also offers a variety of activities that are about winning or losing a little money. One such activity has just caught your attention: a simple card game. As a person interested in puzzles and riddles, you almost instantly started to wonder: Should I pay for such a game? Am I expected to win or lose money while playing it?
This game is played with a standard deck of cards – there are four suits and in each suit cards worth 2 through 10, a Jack, a Queen, a King and an Ace. For the purpose of this problem, the Aces have value 1, Jacks 11, Queens 12, and Kings 13. In other words, each of the values 1 through 13 is present four times in the deck.
The simplest version of this game looks as follows: An employee of the amusement park shuffles the deck uniformly at random and gives you a card. Your winnings are equal to the value of the card.
Here is a more complicated version: As before, the dealer gives you a random card. You now have two options: either you take your winnings, or you return the card you have and ask for another one. The second one is again drawn uniformly at random, and you have to keep it.
The general version of this game has x turns, and you know x in advance. In each turn you can keep the card you have and end the game. In each turn except for the last one you can return the card and ask for another one.
In the easy data set the card you return is always returned back to the deck. Thus the new card you then get is always picked uniformly at random from a deck of 52 cards. In the hard data set the card you return is thrown away, so the more turns you take, the smaller the deck becomes.
Problem specification
You are given the maximal number of turns x. Find the maximum expected amount of money you can win in a single game.
(In other words, find the smallest y with the property: if playing a single game costed more than y, the amusement park would still profit from the game, even if all players played it optimally.)
Input specification
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line. Each test case is given as a single line with a single integer x (between 1 and 52, inclusive).
Output specification
For each test case, output a single line with one real number – the expected amount you will win if you follow an optimal strategy. Output at least 10 decimal places. Any answer with an absolute or relative error at most 10−9 will be accepted.
Example
This is the correct answer both for the easy and the hard version, as for x = 1 they are the same: you have to keep the first card you get. From the 52 cards, each card is picked with probability 1∕52. There are 4 cards having each of the values 1 through 13. Hence the expected value of a card is ∑ i=113i ⋅ (4∕52) = 7.