Sabya is writing code to output a random number between $1$ and $N$ inclusive. The code can output different integers in the interval with different probabilities so that the sum of the probabilities is equal to $1$.

For evaluation, the code is run twice. If the output in both cases are different, his score is equal to the sum of the outputs. Otherwise, his score is equal to $0$.

Sabya is very intelligent, and he writes code that maximizes his expected score. Find the expected score. Output the ratio of the expected score to the maximum possible score. The maximum possible score is $2\times N-1$.

Input Format

The first line contains $\mathbf{T}$: the number of test cases. 

The next $\mathbf{T}$ lines each contain a single integer, $N$.

Output Format

Output $\mathbf{T}$ lines: the ratio $\frac{\text{expected score}}{\text{maximum score}}$ in each case. 

The answer is considered correct if the absolute error is less than $\mathbf{10^{-8}}$.  

Constraints 

$1\leq T\leq10^5$ 

$1\leq N\leq10^6$

Sample Input
3
1
2
3

Sample Output
0.00000000000
0.50000000000
0.54545454545

Explanation

In the first case, the output is always $1$ both times.

In the second case, $1$ and $2$ are generated with the probability of $\frac{1}{2}$ and $\frac{1}{2}$

In the third case, $1$, $2$ and $3$ are generated with the probability of $\frac{5}{22}$, $\frac{4}{11}$ and $\frac{9}{22}$, respectively.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Probability


Solutions:
H = [0]
N_max = 10 ** 6 + 1
for j in range(1, N_max):
	H.append(H[-1] + 1 / j)
maximal_val = [0, 1, 2, 3, 4]
for N in range(5, N_max):
	m = maximal_val[N - 1]
	alpha = (m - 2) / (H[N] - H[N - m])
	while alpha < N - m + 1:
		m += 1
		alpha = (m - 2) / (H[N] - H[N - m])
	m -= 1
	maximal_val.append(m)

def solve(N):
	m = maximal_val[N]
	ans = (N * m - m * (m - 1) // 2 - (m - 2) ** 2 / (H[N] - H[N - m])) / 2
	return ans / (2 * N - 1)

def main():
	Q = int(input().strip())
	for _ in range(Q):
		print('{0:.11f}'.format(solve(int(input().strip())), 10))
main()


h = [0]
for i in range(1, 10 ** 6 + 1):
	h.append(h[-1] + 1.0 / i)

def find_zeros(n):
	small = 0
	big = n
	while small < big:
		mid = (small + big) // 2
		x = (n - mid - 2) / ((mid + 1) * (h[n] - h[mid]))
		if x <= 1:
			big = mid
		else:
			small = mid + 1
	return small

def compute(n):
	s = find_zeros(n)
	return ((n + s + 1) * (n - s) / 4 - (n - s - 2) ** 2 / (2 * h[n] - 2 * h[s])) / (2 * n - 1)
T = int(input())
for t in range(T):
	N = int(input())
	print(compute(N))


H = [0] * 1000001
L = [0] * len(H)
i = 1
T = int(input())
for t in range(T):
	N = int(input())
	while i <= N:
		H[i] = H[i - 1] + 1 / i
		j = L[i - 1]
		while i - j - 2 > (j + 1) * (H[i] - H[j]):
			j += 1
		L[i] = j
		i += 1
	M = L[N]
	print((N * (N + 1) - M * (M + 1) - 2 * (N - M - 2) ** 2 / (H[N] - H[M])) / (8 * N - 4))


from math import log
from math import ceil

def findj(N):
	if N == 1:
		return 1
	elif N == 2:
		return 1
	else:
		start = 1
		end = N
		while start <= end:
			mid = (start + end) // 2
			if mid > (N - mid - 1) / (log(N / (mid - 1)) + 1 / (2 * N) - 1 / (2 * (mid - 1))):
				end = mid - 1
				ans = mid
			else:
				start = mid + 1
	return ans
T = int(input())
EM = 0.5772156649
for _ in range(T):
	N = int(input())
	if N > 10000:
		j = findj(N)
		s = (N * (N + 1) / 2 - j * (j - 1) / 2) / 2
		E = s - (N - j - 1) * (N - j - 1) / (2 * (log(N / (j - 1)) + 1 / (2 * N) - 1 / (2 * (j - 1))))
	else:
		reci = sum([1 / i for i in range(1, N + 1)])
		lambd = (2 * N - 4) / reci
		j = 1
		while 1 / 2 - lambd / (4 * j) < 0:
			reci -= 1 / j
			lambd = (2 * (N - j) - 4) / reci
			j += 1
		s = (N * (N + 1) / 2 - j * (j - 1) / 2) / 2
		E = s - (N - j - 1) * (N - j - 1) / (2 * reci)
	print(E / (2 * N - 1))


def get_harmonic_sums(maxN):
	harmonic_sum = [0 for _ in range(maxN + 1)]
	s = 0
	for i in range(1, maxN + 1):
		s += 1.0 / i
		harmonic_sum[i] = s
	return harmonic_sum

def find_max_k(n, harmonic_sums):
	hsn = harmonic_sums[n]
	if n - 2 <= hsn:
		return n
	(k_min, k_max) = (2, n)
	while k_max - k_min > 1:
		k = (k_max + k_min) // 2
		if k - 2 <= (n - k + 1) * (hsn - harmonic_sums[n - k]):
			k_min = k
		else:
			k_max = k
	return k_min

def solve(n, harmonic_sums):
	if n < 2:
		return 0
	k = find_max_k(n, harmonic_sums)
	expected_score = k * (2 * n - k + 1) / 4 - (k - 2) ** 2 / (2 * (harmonic_sums[n] - harmonic_sums[n - k]))
	return expected_score / (2 * n - 1)
NN = [int(input()) for _ in range(int(input()))]
harmonic_sums = get_harmonic_sums(max(NN))
for N in NN:
	print(solve(N, harmonic_sums))


import math
Harm = [0]
for i in range(1000000):
	Harm.append(Harm[-1] + 1 / (i + 1))
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(0.0)
	else:
		pos = int(2 * math.sqrt(n))
		if n - pos + 1 < (pos - 2) / (Harm[n] - Harm[n - pos]):
			pos -= 1
		probdiv = (pos - 2) / (Harm[n] - Harm[n - pos])
		val = pos * (2 * n - pos + 1) / 4 - (pos - 2) * probdiv / 2
		print(val / (2 * n - 1))


def lambda0(n, k):
	return (n - 1 - k) / (2 * (i_inv_sum[n] - i_inv_sum[k - 1]))

def lambda_k(n):
	k0 = max(n + 1 - int(2 * n ** 0.5), 1)
	l0 = lambda0(n, k0)
	if l0 > 0.5 * k0:
		k0 += 1
		l0 = lambda0(n, k0)
	return (k0, l0)

def max_e_score(n):
	if n == 1:
		return 0
	(k0, lambda0) = lambda_k(n)
	return (n + 1) * n / 4 - k0 * (k0 - 1) / 4 - lambda0 * (n - 1 - k0)
T = int(input())
test_n = [int(input()) for _ in range(T)]
maxn = max(test_n)
i_inv_sum = [0]
for i in range(1, maxn + 1):
	i_inv_sum.append(i_inv_sum[-1] + 1 / i)
for n in test_n:
	print(max_e_score(n) / (2 * n - 1))