Devus and their voting system

All submissions for this problem are available.
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 and Subtasks
Subtask 1 (15 points) 1 ≤ T, n ≤ 7
 1 ≤ T, n ≤ 18
 1 ≤ T, n ≤ 36
Example
Input: 2 1 2 Output: 1.000000 2.000000
Explanation
Example 1: 1^{st} 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.
Author:  admin2 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/DEVVOTE 
Tags  admin2, april15, dynamicprogramming, mediumhard, partitioning 
Date Added:  9032015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 