Toby and the Frog

Statement

Toby the dog is on the cell 0 of a numbered road, TJ the frog is on the cell number X of the same road. Toby wants to catch the frog, but he is not smart enough to count the distance from his current position to X, so he performs the following algorithm:

  • Let pos be the Toby's current position.
  • Jump an integer distance d, where d is uniformly distributed over [1, min(X - pos, 10)].
  • If the new position is the frog's position, catch it and send it as tribute to the queen.
  • In other case start the algorithm again.

Note that the length of Toby's jump cannot be infinite, in fact, it must be less than or equal to 10. Besides this, he will never jump over the frog, in other words, he will never reach a position greater than X. TJ the frog does not want to be catched, due to this, TJ wants to compute the expected number of jumps that Toby needs in order to reach cell number X.

Help to TJ compute this value.

Input:

The input starts with an integer 1 < T ≤ 100 indicating the number of test cases.

Each test case contains one integer 10 ≤ X ≤ 5000 denoting the frog's cell.

Output:

For each test case print in one line the expected number of jumps that Toby needs to reach cell number X.

Answers with absolute error less than 10-6 will be considered correct.

Example input:

2
10
20

Example output:

2.9289682540
4.8740191199

Time and memory limit:

  • 1 second
  • 64MB

Problem source: COJ

s