바클라바 쟁반

ACPC 폐회식에서 참가자들은 한 시즌 내내 고생한 것을 자축하기 위해 아주 큰 바클라바(Baklawa) 쟁반을 주문하기로 했다.

주문을 기다리는 동안 참가자들은 제빵사가 다른 손님들의 쟁반을 만드는 모습을 지켜보기 시작했다. 그는 먼저 넓이가 1인 정N각형을 그리고 그 위에 으깬 헤이즐넛을 뿌린 다음, 그 안에 첫 번째 다각형의 각 변의 중점을 이어 만든 두 번째 다각형을 그리고 그 위에 캐슈넛을 뿌린다. 그런 다음에는 다른 종류의 견과류로 같은 과정을 이어가며, 서로 안쪽에 놓인 정N각형의 무한 수열을 그리는데, 각 다각형은 바로 앞서 그린 다각형의 각 변의 중점을 이어 만든다. 따라서 가장 바깥쪽 다각형에는 한 종류의 견과류(헤이즐넛)가 들어 있고, 두 번째 다각형에는 두 종류(헤이즐넛과 캐슈넛)가 들어 있는 식이다. 이렇게 각 다각형은 그보다 앞선 다각형들의 견과류를 모두 포함한다.

제빵사가 참가자들의 주문을 마치면, 포크를 든 104명이 쟁반의 임의의 위치를 한 번씩 찍는다(그렇다, 샤름 전역의 다른 호텔 사람들도 이 쟁반에 들떠 있었다). 맛 계수는 각 사람의 포크에 맞은 견과류 종류 수를 모두 더해 계산하며, 각 사람마다 독립적으로 계산한다. 어떤 사람이 안쪽에서 i번째 다각형을 찍으면 정확히 i종류의 견과류를 찍는다는 점에 유의하자.

N개의 변을 가진 쟁반의 기대 맛 계수를 구해 지역 대회 감독을 도와주자.

N = 5일 때 처음 세 다각형.

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어지며, 쟁반의 변의 수를 나타내는 정수 N(3 ≤ N ≤ 800)이 주어진다.

각 테스트 케이스마다 해당 테스트 케이스의 기대 맛 계수를 나타내는 소수 하나를 정확히 소수점 아래 5자리로 반올림해 한 줄에 출력한다.

절대 오차 또는 상대 오차가 10−5보다 작으면 정답으로 인정된다.

정N각형은 모든 변의 길이가 같고 모든 내각의 크기가 같은 다각형이다.