Очікування
Ерік створив просту схему для генерації випадкових цілих чисел. Ця схема приймає на вхід ціле число n і генерує рівноймовірні цілі числа в діапазоні від 0 до (n − 1) включно. Наприклад, якщо n = 3, схема генерує числа 0, 1 або 2 з однаковою ймовірністю 1/3.
Тепер Ерік прагне розробити складніші схеми. Перша з них складається з двох незалежних генераторів випадкових чисел, виходи яких обробляються за допомогою операції XOR - побітове виключаюче або.
Друг Еріка, Нік, який вивчає математику, зауважив, що ця схема є досить цікавою, і ще цікавішим є обчислення математичного сподівання результату. Допоможіть їм обчислити це сподівання.
Пам'ятайте, що математичне сподівання випадкової величини визначається як її середнє значення. Для змінної ξ, яка приймає невід'ємні цілі значення, сподівання обчислюється за формулою
де p[i] - ймовірність того, що величина ξ дорівнює i.
Вхідні дані
Перший рядок містить кількість тестів k (1 ≤ k ≤ 1000). Кожен тест представлений одним числом n (1 ≤ n ≤ 10^9) в окремому рядку.
Вихідні дані
Для кожного тесту виведіть в окремому рядку очікуване значення нової схеми Еріка з точністю до двох десяткових знаків.