Read problems statements in Mandarin Chinese and Russian.

Devus are creatures living in Devupur. There are total n Devus in Devupur. i^{th} Devu live in i^{th} house. Houses 1, 2, 3, , , n are placed in a single lane i.e. 1 is a neighbor of 2, 2 is a neighbor of 1 and 3 etc.

They decide their president by a very weird voting system. All the Devus contest in the presidential elections. Each person uniformly randomly votes any of the n person as his preference (he can vote himself too). Devus are really very envious creatures, so no Devu casts his vote to the person whom his neighbor has casted. Devus vote in the increasing order of their IDs.

Finally all the votes are counted and all the Devus having votes equal to highest voted Devu are selected as president.

Now you are interested in finding out expected number of presidents Devupur can select in their upcoming election. Please round the answer to 6 digits after decimal.

------ Input ------

First line of the input contains a single integer T denoting number of test cases.
For each test case, there is a single line containing a single integer n.

------ Output ------

For each test case, print a single real number corresponding to the answer of the problem.

------ Constraints -----

Subtask 1 (15 points)

$1 ≤ T, n ≤ 7$

Subtask 2 (25 points)

$1 ≤ T, n ≤ 18$

Subtask 3 (60 points)

$1 ≤ T, n ≤ 36$

----- Sample Input 1 ------
2

1

2
----- Sample Output 1 ------
1.000000

2.000000
----- explanation 1 ------

Example 1:
1st Devu votes himself and get elected for president. So expected number of presidents are 1.

Example 2:

Both the Devus cast their vote to themselves. So total number of presidents selected are 2.
Devu 1 votes to Devu 2 and Devu 2 votes to Devu 1. In this way, again total total number of presidents selected are 2.
So expected number of presidents selected are (2 + 2) / 2 = 2.

见题面

见题面