바퀴

이 문제에서 다루는 나라에는 꽤 흥미로운 도로 체계가 있다. 이 나라에는 수도와 $n$개의 일반 도시, 모두 $n + 1$개의 도시가 있다. 모든 일반 도시는 수도를 중심으로 하는 원 위에 있다. 이웃한 일반 도시 사이의 거리는 모두 같다. 각 도시는 이웃한 두 도시와 도로로 연결되어 있고, 수도와도 도로로 연결되어 있다. 이 나라를 위에서 내려다보면, 정$n$각형의 꼭짓점이 중심과 연결되어 있는 모습이 보인다.

이 나라에는 힘이 같은 두 야당이 있어서 정권을 잡으려 한다. 게다가 아무도 평화적인 방법으로 정권을 잡으려 하지 않는다! 만일을 대비해 각 도시에는 전차 소대가 하나씩 배치되어 있다. 다음 날이 시작되는 순간 정확히 다음과 같은 일이 일어난다. 각 도시(수도 포함)에서 두 야당 중 하나가 같은 확률로 정권을 장악한다. 그 당은 그 도시에 배치된 전차 소대를 손에 넣는다. 이어서 각 당은 한 곳에 가능한 한 큰 군대를 모을 계획을 세운다. 전차 소대는 도로가 연결하는 두 도시가 모두 같은 당에 의해 점령된 경우에만 도로를 따라 이동할 수 있다.

당신은 역시 정권을 잡으려는 지하 운동의 조직자다. 한 도시에 모일 수 있는 전차 소대 수의 최댓값의 기댓값을 구해야 한다. 조직을 실망시키지 마라!

예를 들어 일반 도시가 세 개 있다고 하자. 그러면 네 도시(일반 도시 세 개와 수도)가 모두 쌍으로 도로로 연결되어 있다. 확률 $1/8$로 모든 도시를 같은 당이 장악한다. 이때 군대의 최대 크기는 4이다. 확률 $3/8$로 두 도시를 한 당이, 나머지 두 도시를 다른 당이 장악한다. 이때 군대의 최대 크기는 2이다. 마지막으로 확률 $1/2$로 한 도시에서는 한 당이, 나머지 세 도시에서는 다른 당이 정권을 잡는다. 이때 군대의 최대 크기는 3이다. 이 경우 답의 기댓값은 $4\times1/8+2\times3/8+3\times1/2=2.75$이다.

첫째 줄에는 테스트 예제의 수를 나타내는 양의 정수 $t$가 주어진다. 다음 $t$개의 줄에는 정수 $n$($3 \le n \le 500$)이 하나씩 주어지며, 이는 나라에 있는 일반 도시의 수이다. 모든 테스트 예제의 일반 도시 수 합은 1000을 넘지 않는다.

각 테스트 예제마다 한 도시에 모일 수 있는 소대 수의 최댓값의 기댓값을 한 줄에 출력한다. 답이 정답과 $10^{-9}$ 이하로 차이 나면 정답으로 인정된다.