Эрик построил простую схему генерации произвольных целых чисел. Его схема принимает на вход целое число n и генерирует одинаково распределенные целые числа между 0 и (n − 1) включительно. Например, если n = 3, то схема генерирует каждое из чисел 0, 1 или 2 с одинаковой вероятностью 1/3.

Теперь Эрик хочет построить более сложные схемы. Первая их них будет состоять из двух независимых вероятностных генераторов, выходы которых пропускаются через операцию XOR - побитовое исключающее или.

Друг Эрика Ник изучает математику. Ник сказал, что эта схема довольно интересная, а еще более интересным является математическое ожидание результата. Помогите им его вычислить.

Помните, что ожидание вероятностной величины определяется как ее среднее значение. Для переменной ξ, принимающей неотрицательные целые числа, ожидание вычисляется как

где pi - вероятность величины ξ равняться i.

Входные данные

Первая строка содержит количество тестов k (1 ≤ k ≤ 1000). Каждый тест содержит одно число n (1 ≤ n ≤ 109) в отдельной строке.

Выходные данные

Для каждого теста вывести в отдельной строке ожидаемое значение новой схемы Эрика с двумя десятичными знаками.