Колесо
Країна, про яку йде мова у цій задачі, має досить цікаву систему доріг. Усього у цій країні 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}.