Колесо
Страна, о которой идет речь в этой задаче, имеет довольно интересную систему дорог. Всего в этой стране 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}.