시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB0000.000%

문제

Страна, о которой идет речь в этой задаче, имеет довольно интересную систему дорог. Всего в этой стране n + 1 город — столица и n обычных городов. Все обычные города расположены на окружности, центр которой находится в столице. Расстояние между всеми соседними обычными городами одинаковое. Каждый город соединен дорогами с двумя своими соседями, а также со столицей. Если бы мы посмотрели сверху на эту страну, то увидели бы правильный n-угольник, вершины которого соединены с центром.

В этой стране существует две одинаково сильные оппозиционные партии, которые хотят захватить власть в стране. Причем никто не хочет делать это мирным путем! В каждом городе на всякий случай расположен танковый взвод. Ровно в момент начала следующего дня произойдет следующее. В каждом городе (включая столицу) с одинаковой вероятностью захватит власть одна из оппозиционных партий. В распоряжении этой партии оказывается танковый взвод, расположенный в этом городе. Далее каждая партия планирует собрать в одном месте армию как можно большего размера. Танковый взвод может проехать по дороге только в том случае, если оба города, которые соединяет дорога, захвачены одной и той же партией.

Вы являетесь организатором подпольного движения, которое тоже хочет захватить власть. Вам необходимо узнать математическое ожидание наибольшего количества танковых взводов, которые смогут оказаться в одном городе. Не подведите свою организацию!

Например, пусть есть три обычных города. Тогда все четыре города (три обычных и столица) попарно соединены дорогами. Тогда с вероятностью 1/8 все города захватит одна и та же партия. В этом случае максимальный размер армии равен 4. С вероятностью 3/8 два города будут захвачены одной партией, и два — другой. В этом случае максимальный размер армии равен 2. Наконец, с вероятностью 1/2 в одном городе власть захватит одна партия, а в трех других — другая. В этом случае максимальный размер армии будет равен 3. Математическое ожидание ответа в этом случае 4×1/8+2×3/8+3×1/2=2.75.

입력

Первая строка содержит целое положительное число t — количество тестовых примеров. Следующие t строк содержат по одному целому числу n (3 ≤ n ≤ 500) — количество обычных городов в стране. Гарантируется, что суммарное количество обычных городов во всех тестовых примерах не превышает 1000.

출력

Для каждого тестового примера выведите одно число — математическое ожидание наибольшего количества взводов, которые могут оказаться в одном городе. Ответ считается правильным, если он отличается от правильного не более чем на 10-9.

예제 입력 1

2
3
4

예제 출력 1

2.75
3.4375