Have you ever implemented a program adding two big integers that cannot be represented by the primitive data type of your programming language? The algorithm is just simulation of the column addition method that we have been taught in elementary school. Sometimes we forget the carry and the result is incorrect. 
In this problem, you need to evaluate the expected value of the number of times we have non-zero carry when adding two non-negative integers that contain at most N digits each. Note that we are adding the numbers in their base 10 representation.

For example, the following table shows the number of carries when adding some pairs of numbers: 

A
		B		
		Number of carries
	20
		4		
		0
	111
		119		
		1
	123
		923		
		1
	1235
		98765		
		5
	
------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. 
Each test case has a single line containing an integer N.

------ Output ------ 

For each test case, output a single line containing the required expected value. 
Your answer will be accepted if the error is less than 10 ^{-6}.

------ Constraints ------ 

$1 ≤ T ≤ 100,000(10^{5})$
$1 ≤ N ≤ 100,000(10^{5})$

----- Sample Input 1 ------ 
3
1
2
3
----- Sample Output 1 ------ 
0.45
0.945
1.4445
----- explanation 1 ------ 
Example case 1.
We have 10*10 = 100 cases of adding two 1-digit number.
The carry appears when adding 1 and 9, 2 and 9, 3 and 9 ... and so on, 
there are 45 cases in total and in each case, the carry appears exactly once.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
p = 10 ** 5 + 9
(dp, pre) = ([0] * p, [0] * p)
dp.append(0)
dp.append(0.45)
for i in range(2, p):
	dp[i] = 0.45 + 10 * dp[i - 1] / 100
for i in range(1, p):
	pre[i] = pre[i - 1] + dp[i]
for _ in range(int(input())):
	print(pre[int(input()) + 1])


dp = [0] * 100000
dp[0] = 0.45
for i in range(1, 100000):
	dp[i] = dp[i - 1] + 0.5 - 5 * pow(10, -(i + 2))
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	print('{0:.6f}\n'.format(dp[n - 1]))


def AaddBCarryOvers(A, B):
	C = 0
	carryOvers = 0
	column = 0
	lastCarryOver = 0
	while A != 0 or B != 0:
		newValue = A % 10 + B % 10
		A //= 10
		B //= 10
		if newValue + lastCarryOver >= 10:
			carryOvers += 1
		C += newValue * 10 ** column
		column += 1
		lastCarryOver = (newValue + lastCarryOver) // 10
	return carryOvers
answers = [0]
x = 0
for i in range(1, 10 ** 2):
	x += i * 10 ** (i - 1)
	answers.append(x * 45 / 10 ** (i + 1))
T = int(input())
for _ in range(T):
	N = int(input())
	if N < 100:
		print(answers[N])
	else:
		print(N / 2 - 1 / 18)


def solve(n):
	ans = 0
	for i in range(n, 0, -1):
		ans += i / pow(10, n - i)
		if n - i == 10:
			break
	return 0.45 * ans
for _ in range(int(input())):
	print(solve(int(input())))


N = 100005
T = int(input())
prob_carry = [0 for i in range(N)]
for i in range(1, N):
	prob_carry[i] = prob_carry[i - 1] * 0.1 + 0.45
for i in range(1, N):
	prob_carry[i] += prob_carry[i - 1]
for i in range(T):
	n = int(input())
	print(f'{prob_carry[n]:.8f}')


def solve():
	n = int(input())
	if n <= 7:
		x = '1' * n
		x = int(x) / 10 ** n
	else:
		x = '1' * 7
		x = int('1' * 7) / 10 ** 7
	return (n - x) / 2
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	if n <= 6:
		if n == 1:
			print(0.45)
		elif n == 2:
			print(0.945)
		elif n == 3:
			print(1.4445)
		elif n == 4:
			print(1.94445)
		elif n == 5:
			print(2.444445)
		else:
			print(2.9444445)
	elif n % 2 == 1:
		print(str(n // 2) + '.444444444')
	else:
		print(str(n // 2 - 1) + '.944444444')


k = 10 ** 5 + 9
aman = [0] * k
aman.append(0)
aman.append(0.45)
for i in range(2, k):
	aman[i] = 0.45 + 10 * aman[i - 1] / 100
ravan = [0] * k
for i in range(1, k):
	ravan[i] = ravan[i - 1] + aman[i]
for _ in range(int(input())):
	n = int(input())
	print(ravan[n + 1])


def solve():
	n = int(input())
	if n == 1:
		return 0.45
	if n == 2:
		return 0.945
	if n == 3:
		return 1.4445
	if n == 4:
		return 1.94445
	if n == 5:
		return 2.444445
	if n == 6:
		return 2.9444445
	if n % 2 == 1:
		return n // 2 + 0.444444444
	else:
		return n // 2 - 1 + 0.944444444
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	x = 0
	for i in range(1, n + 1):
		x += 1 / pow(10, i)
		if i > 6:
			break
	print((n - x) / 2)


a = 10 ** 5 + 9
z = [0] * a
z.append(0)
z.append(0.45)
for i in range(2, a):
	z[i] = 0.45 + 10 * z[i - 1] / 100
f = [0] * a
for i in range(1, a):
	f[i] = f[i - 1] + z[i]
for _ in range(int(input())):
	n = int(input())
	print(f[n + 1])


for _ in range(int(input())):
	n = int(input())
	if n < 7:
		x = float('0.' + '1' * n)
	else:
		x = float('0.' + '1' * 7)
	print((n - x) / 2)


for _ in range(int(input())):
	n = int(input())
	if n < 7:
		x = (1 - 1 / 10 ** n) / 9
	else:
		x = (1 - 1 / 10 ** 7) / 9
	print((n - x) / 2)


dp = []
dp.append(0)
dp.append(45 / 100)
for i in range(2, 100001):
	val = 10 / 100 * dp[-1]
	val += 45 / 100
	dp.append(val)
s = []
s.append(0)
for i in range(1, 100001):
	s.append(dp[i] + s[i - 1])
for t in range(int(input())):
	n = int(input())
	print('%.6f' % s[n])


t = int(input(''))
b = []
for i in range(0, t):
	n = int(input(''))
	m = (9 * n - 1 + 10.0 ** (-n)) / 18
	b.append(m)
for j in range(0, t):
	print(round(b[j], 6))


a = [0.45, 0.945, 1.4445, 1.94445]
a1 = 0.444444
a2 = 0.944444
for _ in range(int(input())):
	n = int(input())
	if n <= 4:
		print(a[n - 1])
	elif n % 2 == 1:
		print(a1 + n // 2)
	else:
		print(a2 + (n - 1) // 2)


Solutions = [0] * 100001
for i in range(1, 100):
	Solutions[i] = 0.5 - 1 / (2 * pow(10, i)) + Solutions[i - 1]
for i in range(100, 100001):
	Solutions[i] = Solutions[i - 1] + 0.5
cases = int(input())
for i in range(cases):
	case = int(input())
	print(str(Solutions[case]))


t = int(input())
for it in range(t):
	n = int(input())
	res = (9 * n - 1 + 10.0 ** (-n)) / 18
	print(res)


a = 10 ** 5 + 9
initial = [0] * a
initial.append(0)
initial.append(0.45)
for i in range(2, a):
	initial[i] = 0.45 + 10 * initial[i - 1] / 100
final = [0] * a
for i in range(1, a):
	final[i] = final[i - 1] + initial[i]
for _ in range(int(input())):
	n = int(input())
	print(final[n + 1])


d = {1: 0.45}
for i in range(2, 10 ** 5 + 1):
	d[i] = 0.45 + 0.1 * d[i - 1]
f = [0]
for i in range(1, 10 ** 5 + 1):
	f.append(d[i] + f[-1])
t = int(input())
for _ in range(t):
	n = int(input())
	print(f[n])