Wheel

The country in this problem has a rather interesting road system. There are $n + 1$ cities in total: the capital and $n$ ordinary cities. All ordinary cities lie on a circle centered at the capital. The distance between any two neighboring ordinary cities is the same. Every city is connected by roads to its two neighbors and to the capital. Viewed from above, the country looks like a regular $n$-gon whose vertices are connected to the center.

Two equally strong opposition parties want to seize power in this country. Nobody wants to do it peacefully! For safety, each city holds one tank platoon. Exactly at the start of the next day the following happens. In each city (including the capital), one of the opposition parties seizes power with equal probability. That party takes control of the tank platoon stationed in that city. Then each party plans to gather an army of the largest possible size in one place. A tank platoon can drive along a road only if both cities that the road connects are captured by the same party.

You organize an underground movement that also wants to seize power. You need to find the expected value of the largest number of tank platoons that can end up in one city. Do not let your organization down!

For example, suppose there are three ordinary cities. Then all four cities (three ordinary cities and the capital) are pairwise connected by roads. With probability $1/8$ the same party captures all cities. In this case the maximum army size is 4. With probability $3/8$, two cities are captured by one party and two by the other. In this case the maximum army size is 2. Finally, with probability $1/2$, one party seizes power in one city and the other party in the other three. In this case the maximum army size is 3. The expected value of the answer here is $4\times1/8+2\times3/8+3\times1/2=2.75$.

The first line contains a positive integer $t$, the number of test cases. The next $t$ lines each contain a single integer $n$ ($3 \le n \le 500$), the number of ordinary cities in the country. The total number of ordinary cities over all test cases does not exceed 1000.

For each test case, output a single number: the expected value of the largest number of platoons that can end up in one city. An answer is accepted if it differs from the correct one by at most $10^{-9}$.