Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef is so good at programming that he won almost all competitions. With all the prizes, Chef bought a new house. The house looks like a grid of size N (1-indexed) which consists of N × N rooms containing diamonds. For each room, the room number is equal to the sum of the row number and the column number.
The number of diamonds present in each room is equal to the absolute difference between the sum of even digits and sum of odd digits in its room number. For example, if the room number is 3216, then the number of diamonds present in that room will be |(2+6)-(3+1)| = 4.
You are given the number N. You have to print the total number of diamonds present in Chef's house.

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains a single integer N.

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

For each test case, print the answer on a separate line.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{6}$

------ Subtasks ------ 

Subtask #1 (15 points):

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 1000$

Subtask #2 (15 points):

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{6}$

Subtask #3 (70 points): original constraints

----- Sample Input 1 ------ 
3
1
2
3
----- Sample Output 1 ------ 
2
12
36
----- explanation 1 ------ 
Example case 3: There are 9 rooms. Room (1,1) has number 2, room (1,2) has number 3, etc. For each room, the number of diamonds in it is equal to the room number, so the total number of diamonds present is (2+3+4+3+4+5+4+5+6) = 36.

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

Starter code:

Solutions:
from itertools import repeat

def f(x):
	osum = 0
	esum = 0
	while x > 0:
		d = x % 10
		if d % 2 == 0:
			esum += d
		else:
			osum += d
		x = x // 10
	return abs(osum - esum)
diamonds = list(repeat(0, 1000001))
prefix = list(repeat(0, 2000001))
for i in range(1, len(prefix)):
	prefix[i] = prefix[i - 1] + f(i)
for i in range(1, len(diamonds)):
	diamonds[i] = diamonds[i - 1] + 2 * (prefix[2 * i - 1] - prefix[i]) + f(2 * i)
t = int(input())
for _ in range(t):
	n = int(input())
	print(diamonds[n])


def check(n):
	sum1 = 0
	sum2 = 0
	while n > 0:
		a = n % 10
		if a % 2 == 0 or a == 0:
			sum1 += a
		else:
			sum2 += a
		n = n // 10
	return abs(sum1 - sum2)
dp = [0] * 1000001
summation = [0] * 2000002
for i in range(1, 2000002):
	summation[i] = summation[i - 1] + check(i)
for i in range(1, 1000001):
	dp[i] = dp[i - 1] + 2 * (summation[2 * i - 1] - summation[i]) + check(2 * i)
t = int(input())
while t > 0:
	n = int(input())
	print(dp[n])
	t = t - 1


N = 10 ** 6 + 5
dp = [0] * N

def getValue(K):
	(even, odd) = (0, 0)
	while K > 0:
		d = K % 10
		if d & 1 == 1:
			odd += d
		else:
			even += d
		K = K // 10
	return abs(even - odd)

def solve():
	value = [0] * (2 * N)
	for i in range(0, 2 * N):
		value[i] = getValue(i)
	prefix = value[:]
	for i in range(1, 2 * N):
		prefix[i] += prefix[i - 1]
	for i in range(0, N - 1):
		dp[i] = dp[i - 1] + 2 * (prefix[2 * i] - prefix[i]) - value[2 * i]
solve()
T = int(input())
for _ in range(T):
	n = int(input())
	print(dp[n])


def ret_res(ele):
	tot = 0
	while ele > 0:
		if ele & 1 == 1:
			tot -= ele % 10
		else:
			tot += ele % 10
		ele = ele // 10
	return abs(tot)
fun = [0 for _ in range(2 * 10 ** 6 + 1)]
for i in range(2, 2 * 10 ** 6 + 1):
	fun[i] = ret_res(i) + fun[i - 1]
dp = [0 for _ in range(10 ** 6 + 1)]
dp[1] = 2
for i in range(2, 10 ** 6 + 1):
	dp[i] = fun[2 * i] - 2 * fun[i] + fun[2 * i - 1] + dp[i - 1]
for i in range(int(input())):
	n = int(input())
	print(dp[n])


def zero(a, odd=0, even=0):
	while a:
		ans = a % 10
		if ans % 2 == 0:
			even += ans
		else:
			odd += ans
		a //= 10
	return abs(odd - even)
length = [0, 2]
for y in range(2, 2000001):
	length.append(length[y - 1] + zero(y + 1))
final = [0, 2]
for y in range(2, 1000001):
	final.append(final[y - 1] + 2 * length[2 * y - 2] - 2 * length[y - 1] + zero(2 * y))
for _ in range(int(input())):
	n = int(input())
	print(final[n])


def digits(t):
	odd = 0
	even = 0
	while t:
		ans = t % 10
		if ans % 2 == 0:
			even += ans
		else:
			odd += ans
		t //= 10
	return abs(even - odd)
maxi = 1000000
numbers = [0 for _ in range(maxi * 2 + 1)]
numbers[1] = 2
for i in range(2, 2 * maxi + 1):
	numbers[i] = numbers[i - 1] + digits(i + 1)
area = [0 for _ in range(maxi + 1)]
area[1] = 2
for i in range(2, maxi + 1):
	area[i] = area[i - 1] + 2 * numbers[2 * i - 2] - 2 * numbers[i - 1] + digits(2 * i)
for _ in range(int(input())):
	n = int(input())
	print(area[n])


def fun(n):
	s1 = 0
	s2 = 0
	while n > 0:
		if n % 2 == 0:
			s1 += n % 10
		else:
			s2 += n % 10
		n = n // 10
	return abs(s1 - s2)
dp = [0]
k = 1000000
x = [0]
dp1 = [0]
for i in range(2, k * 2 + 1):
	dp.append(fun(i))
	dp1.append(dp1[len(dp1) - 1] + dp[len(dp) - 1])
an = [0, 2, 12]
for i in range(3, k + 1):
	an.append(an[len(an) - 1] + (dp1[(i - 1) * 2 - 1] - dp1[i - 1]) * 2 + dp[i * 2 - 1] + dp[i * 2 - 2] * 2)
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	print(an[n])


def f(n):
	even = odd = 0
	while n > 0:
		d = n % 10
		n = n // 10
		if d % 2 == 0:
			even += d
		else:
			odd += d
	return abs(even - odd)
n = 1000000
dp = [0] * (n + 1)
rooms = [0] * (2 * n + 1)
for i in range(1, len(rooms)):
	rooms[i] = rooms[i - 1] + f(i)
for i in range(1, n + 1):
	dp[i] = dp[i - 1] + (rooms[2 * i - 1] - rooms[i]) * 2 + f(2 * i)
t = int(input())
for _ in range(t):
	n = int(input())
	print(dp[n])


(prefix, diamonds) = ([0 for _ in range(2000002)], [0 for _ in range(1000001)])

def fun(num):
	(es, os) = (0, 0)
	while num:
		if not num % 10 % 2:
			es += num % 10
		else:
			os += num % 10
		num //= 10
	return abs(es - os)
for i in range(1, 2000002):
	prefix[i] = prefix[i - 1] + fun(i)
for i in range(1, 1000001):
	diamonds[i] = diamonds[i - 1] + 2 * (prefix[2 * i] - prefix[i]) - fun(2 * i)
n = int(input())
for _ in range(n):
	t = int(input())
	print(diamonds[t])


def f(number):
	odd_sum = 0
	even_sum = 0
	while number > 0:
		digit = number % 10
		if digit % 2 == 0:
			even_sum += digit
		else:
			odd_sum += digit
		number = number // 10
	return abs(even_sum - odd_sum)
row = [1]
for i in range(2, 2000001):
	row.append(row[-1] + f(i))
diamonds = [2]
for i in range(1, 1000000):
	diamonds.append(diamonds[i - 1] + 2 * (row[2 * i] - row[i]) + f(2 * i + 2))
for i in range(int(input())):
	print(diamonds[int(input()) - 1])


def cal(n1):
	o = e = 0
	while n1 > 0:
		k = n1 % 10
		n1 //= 10
		if k % 2 == 0:
			e += k
		else:
			o += k
	return abs(o - e)
last = [0 for _ in range(2000002)]
diamonds = [0 for _ in range(1000001)]
for i in range(1, 2000002):
	last[i] = last[i - 1] + cal(i)
for i in range(1, 1000001):
	diamonds[i] = diamonds[i - 1] + 2 * (last[2 * i] - last[i]) - cal(2 * i)
for t in range(int(input())):
	n = int(input())
	print(diamonds[n])


import math

def f(n):
	oddsum = evensum = 0
	while n > 0:
		k = n % 10
		n //= 10
		if k % 2 == 0:
			evensum += k
		else:
			oddsum += k
	return abs(oddsum - evensum)
n = 1000000
l = [0] * (n + 1)
prefix = [0] * (2 * n + 1)
for i in range(1, len(prefix)):
	prefix[i] = prefix[i - 1] + f(i)
for i in range(1, n + 1):
	l[i] = l[i - 1] + (prefix[2 * i - 1] - prefix[i]) * 2 + f(2 * i)
t = int(input())
while t:
	t -= 1
	k = int(input())
	print(l[k])


N = 1000003
g = [0, 1]
for i in range(2, 2 * N + 10):
	s = 0
	while i > 0:
		r = i % 10
		if r % 2 == 0:
			s += r
		else:
			s -= r
		i = i // 10
	s = abs(s)
	g.append(s)
S = [4, 14]
for i in range(1, N):
	s_i = S[i] - 2 * g[i + 2] + 2 * g[2 * i + 3] + 2 * g[2 * i + 4]
	S.append(s_i)
f = [0, 2]
for i in range(1, N):
	f_n = f[i] + S[i] - g[2 * i + 2]
	f.append(f_n)
for _ in range(int(input())):
	print(f[int(input())])


def fn(n):
	o = e = 0
	while n:
		if n % 10 % 2 == 0:
			e += n % 10
		else:
			o += n % 10
		n //= 10
	return abs(o - e)
d = [0]
for i in range(1, 2000002):
	d.append(fn(i))
pref = [0]
for i in range(1, 2000002):
	pref.append(pref[-1] + d[i])
ans = [2]
for i in range(2, 1000001):
	ans.append(ans[-1] + 2 * (pref[2 * i - 1] - pref[i]) + d[2 * i])
for t in range(int(input())):
	print(ans[int(input()) - 1])


M = 2000001
N = 1000001
diamonds = [0] * N
a = [0] * M
b = [0] * M
for i in range(M):
	(o, e) = (0, 0)
	x = i
	while x:
		z = x % 10
		if not z % 2:
			e += z
		else:
			o += z
		x //= 10
	a[i] = abs(o - e)
for i in range(2, M):
	b[i] = b[i - 1] + a[i]
diamonds[1] = 2
for i in range(2, N):
	diamonds[i] = diamonds[i - 1] + (b[i * 2] * 2 - b[i] * 2 - a[i * 2])
for i in range(int(input())):
	m = int(input())
	print(diamonds[m])


mat = [0] * 1000001
pre = [0] * 2000001

def f(x):
	oddsum = 0
	evensum = 0
	while x:
		digit = x % 10
		if digit % 2 == 0:
			evensum += digit
		else:
			oddsum += digit
		x = x // 10
	return abs(oddsum - evensum)
for i in range(1, len(pre)):
	pre[i] = pre[i - 1] + f(i)
for i in range(1, len(mat)):
	mat[i] = mat[i - 1] + (pre[2 * i - 1] - pre[i]) * 2 + f(2 * i)
for _ in range(int(input())):
	n = int(input())
	print(mat[n])


even = [0] * 2000009
odd = [0] * 2000009
Ar = [0] * 2000009
for i in range(1, 10):
	if i % 2 == 0:
		even[i] = i
	else:
		odd[i] = i
	Ar[i] = Ar[i - 1] + abs(even[i] - odd[i])
for i in range(10, 2000009):
	even[i] = even[i % 10] + even[i // 10]
	odd[i] = odd[i % 10] + odd[i // 10]
	Ar[i] = Ar[i - 1] + abs(even[i] - odd[i])
A = [0] * 1000003
for i in range(1, 1000003):
	A[i] = A[i - 1] + Ar[i * 2] + Ar[2 * i - 1] - 2 * Ar[i]
for _ in range(int(input())):
	print(A[int(input())])


def fun(x):
	esum = 0
	osum = 0
	while x != 0:
		if x % 2 == 0:
			esum += x % 10
		else:
			osum += x % 10
		x = x // 10
	return abs(osum - esum)
Ar = [0] * 2000009
for i in range(1, 2000009):
	Ar[i] = Ar[i - 1] + fun(i)
A = [0] * 1000003
for i in range(1, 1000003):
	A[i] = A[i - 1] + Ar[i * 2] + Ar[2 * i - 1] - 2 * Ar[i]
for _ in range(int(input())):
	print(A[int(input())])


def num(n):
	c1 = 0
	c2 = 0
	while n:
		d = n % 10
		if d % 2 == 0:
			c1 += d
		else:
			c2 += d
		n = n // 10
	return abs(c1 - c2)
l1 = [num(i) for i in range(2 * 10 ** 6 + 2)]
sumarr = [0]
for i in range(1, 2 * 10 ** 6 + 1):
	sumarr.append(sumarr[-1] + l1[i + 1])
ans = [0]
for i in range(1, 10 ** 6 + 1):
	ans.append(ans[-1] + l1[2 * i] + 2 * (sumarr[2 * i - 2] - sumarr[i - 1]))
for i in range(int(input())):
	n = int(input())
	print(ans[n])


import gc
gc.disable()

def main():
	from sys import stdin, stdout
	import atexit, io, sys
	buffer = io.StringIO()
	sys.stdout = buffer

	@atexit.register
	def write():
		sys.__stdout__.write(buffer.getvalue())
	ans = [0] * 1000001
	ans[1] = 2
	llSum = 2
	ress = [0] * 2 * 1000001
	for y in range(10):
		ress[y] = y if y % 2 else -y
	for y in range(10, 2 * 1000001):
		ress[y] = ress[y % 10] + ress[y // 10]
	for x in range(2, 1000001):
		llSum = llSum - abs(ress[x]) + abs(ress[x * 2 - 1]) + abs(ress[x * 2])
		ans[x] = ans[x - 1] + llSum * 2 - abs(ress[x * 2])
	t = int(stdin.readline())
	stdout.write('\n'.join((str(ans[int(n)]) for n in stdin.readlines())))
main()


def diamonds(cell):
	d = 0
	while cell != 0:
		if cell % 2 == 0:
			d += cell % 10
		else:
			d -= cell % 10
		cell = int(cell / 10)
	if d < 0:
		return -d
	return d
ls = [0] * 2000010
for i in range(1, len(ls)):
	ls[i] = ls[i - 1] + diamonds(i)
d = [0] * (int(len(ls) / 2) - 2)
for i in range(1, len(d)):
	d[i] = d[i - 1] + ls[i + i] + ls[i + i - 1] - 2 * ls[i]
t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	print(d[n])


N = 1000000

def diam(i):
	res = 0
	x = i
	while True:
		y = x % 10
		if y % 2 == 0:
			res += y
		else:
			res -= y
		x //= 10
		if x == 0:
			break
	return abs(res)
dia = list(map(diam, range(2 * N + 1)))
diamond = list(range(N + 1))
diamond[1] = (2, 0)
diamond[2] = (12, 10)
for i in range(3, N + 1):
	x = diamond[i - 1][1] - 2 * dia[i] + dia[2 * i - 2] + 2 * dia[2 * i - 1] + dia[2 * i]
	diamond[i] = (diamond[i - 1][0] + x, x)
t = int(input())
for _ in range(t):
	n = int(input())
	print(diamond[n][0])


oddarr = [0] * 2000219
evenarr = [0] * 2000219
diff = [0] * 2000219
sudiff = [0] * 2000219
oddarr[0] = 0
evenarr[0] = 1
for i in range(1, 10, 1):
	oddnow = 0
	evennow = 0
	if i % 2 == 0:
		evennow = i
	else:
		oddnow = i
	oddarr[i] = oddnow
	evenarr[i] = evennow
	diff[i] = abs(oddarr[i] - evenarr[i])
for i in range(10, 2000219):
	ele = i % 10
	oddnow = oddarr[i // 10]
	evennow = evenarr[i // 10]
	if ele % 2 == 0:
		evennow += ele
	else:
		oddnow += ele
	oddarr[i] = oddnow
	evenarr[i] = evennow
	diff[i] = abs(oddarr[i] - evenarr[i])
sudiff[0] = 0
sudiff[1] = 2
for i in range(2, 2000219):
	sudiff[i] = sudiff[i - 1] + diff[i]
ansarr = [0] * 2000219
ansarr[0] = 0
ansarr[1] = 2
for i in range(2, 1000109):
	ansarr[i] = ansarr[i - 1] + 2 * (sudiff[2 * i] - sudiff[i]) - diff[2 * i]
for _ in range(int(input())):
	n = int(input())
	print(ansarr[n])


list1 = []
for _ in range(int(input())):
	M = int(input())
	list1.append(M)
mentos = max(list1)
array = [0, 0]
array1 = [0, 0]
for i in range(2, 2 * mentos + 1):
	answer = i
	array4 = 0
	array5 = 0
	while answer:
		values = answer % 10
		answer = answer // 10
		if values % 2 == 0:
			array4 += values
		else:
			array5 += values
	addition = int(abs(array4 - array5))
	array.append(addition)
	array1.append(array1[-1] + addition)
array2 = [0, 2]
for i in range(2, mentos + 1):
	array2.append((array1[2 * i - 1] - array1[i]) * 2 + array[2 * i] + array2[-1])
for M in list1:
	print(array2[M])


arr = []
for _ in range(int(input())):
	N = int(input())
	arr.append(N)
mint = max(arr)
hello = [0, 0]
hello1 = [0, 0]
for i in range(2, 2 * mint + 1):
	number = i
	hello4 = 0
	hello5 = 0
	while number:
		digit = number % 10
		number = number // 10
		if digit % 2 == 0:
			hello4 += digit
		else:
			hello5 += digit
	differ = int(abs(hello4 - hello5))
	hello.append(differ)
	hello1.append(hello1[-1] + differ)
hello2 = [0, 2]
for i in range(2, mint + 1):
	hello2.append((hello1[2 * i - 1] - hello1[i]) * 2 + hello[2 * i] + hello2[-1])
for N in arr:
	print(hello2[N])


M = 2000001
N = 1000000
d = [0] * M
a = [0] * M
b = [0] * N
for i in range(1, M):
	(n, e, o) = (i, 0, 0)
	while n > 0:
		m = n % 10
		if m % 2:
			o += m
		else:
			e += m
		n //= 10
	d[i] = abs(e - o)
for i in range(2, M):
	a[i] = a[i - 1] + d[i]
b[1] = 2
for i in range(2, N):
	b[i] = b[i - 1] + a[i * 2] * 2 - a[i] * 2 - d[i * 2]
t = int(input())
for i in range(t):
	z = int(input())
	print(b[z])


import sys
sys.setrecursionlimit = 2000001

def number_of_diamonds(room_number):
	(even_sum, odd_sum) = (0, 0)
	while room_number:
		digit = room_number % 10
		if digit % 2:
			even_sum += digit
		else:
			odd_sum += digit
		room_number //= 10
	return abs(even_sum - odd_sum)
assert number_of_diamonds(room_number=3316) == 1
assert number_of_diamonds(room_number=0) == 0
assert number_of_diamonds(room_number=10) == 1
DIAMONDS = [number_of_diamonds(room_number=room_number) for room_number in range(2000001)]
prefixSum = [0] * 2000001
for i in range(1, 2000001):
	prefixSum[i] = prefixSum[i - 1] + DIAMONDS[i]
assert prefixSum[4] == 10
cache = {}
cache[1] = 2
cache[2] = 12

def total_diamonds(num):
	if num in cache:
		return cache[num]
	else:
		cache[num] = 2 * (prefixSum[2 * num - 1] - prefixSum[num]) + DIAMONDS[2 * num] + total_diamonds(num=num - 1)
	return cache[num]
for i in range(1, 1000001):
	total_diamonds(num=i)
T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	print(total_diamonds(num=N))


arr = []
arr.append(0)
for i in range(1, 2000001):
	even = 0
	odd = 0
	j = i
	while j > 0:
		if j % 10 % 2 == 0:
			even += j % 10
		else:
			odd += j % 10
		j = j // 10
	arr.append(abs(even - odd))
dmd = []
dmd.append(0)
dmd.append(2)
dmd.append(12)
dmd.append(36)
for i in range(4, 1000001):
	dmd.append(arr[2 * i] + 2 * arr[2 * i - 1] - dmd[i - 2] - 2 * arr[i] + 2 * dmd[i - 1] + arr[2 * (i - 1)])
t = int(input())
for i in range(t):
	print(dmd[int(input())])


from itertools import *
diamonds = [abs(sum((d if d % 2 == 0 else -d for d in map(int, str(n))))) for n in range(2 * 10 ** 6 + 1)]
cumonds = list(accumulate(diamonds))
solve = [0, 2] + [0] * (2 * 10 ** 6)
for i in range(2, 10 ** 6 + 1):
	solve[i] = solve[i - 1] + (cumonds[i * 2] - cumonds[i]) * 2 - diamonds[i * 2]
for _ in range(int(input())):
	x = int(input())
	print(solve[x])


MAX_VAL = 10 ** 6 * 2 + 1
D = [0] * MAX_VAL
E = [0] * MAX_VAL
for i in range(1, MAX_VAL):
	xx = 1 + i
	t = [0, 0]
	while xx != 0:
		xxx = xx % 10
		xx //= 10
		t[xxx % 2] += xxx
	D[i] = D[i - 1] + abs(t[0] - t[1])
N = 10
for i in range(1, 10 ** 6 + 1):
	E[i] = E[i - 1] + D[2 * i - 1] + D[2 * i - 2] - 2 * D[i - 1]
T = int(input())
for t in range(T):
	print(E[int(input())])


ans = [0] * 2000005
anr = [0] * 2000005
A = [0] * 1000005
for i in range(10):
	if i % 2 == 0:
		ans[i] = ans[i] + i
	else:
		ans[i] = ans[i] - i
anr[0] = 0
for i in range(10, 2000005):
	n = i
	d = n % 10
	f = n // 10
	if d % 2 == 0:
		ans[n] = ans[f] + d
	else:
		ans[n] = ans[f] - d
for i in range(0, 2000005):
	if ans[i] < 0:
		ans[i] = ans[i] * -1
for i in range(1, 2000005):
	anr[i] = anr[i - 1] + ans[i]
A[0] = 0
A[1] = ans[2]
for i in range(2, 1000002):
	A[i] = A[i - 1]
	A[i] = A[i] + 2 * (anr[2 * i - 1] - anr[i])
	A[i] = A[i] + ans[2 * i]
for _ in range(int(input())):
	n = int(input())
	print(A[n])


b = []
for i in range(0, 2 * 10 ** 6 + 1):
	temp = i
	ec = oc = 0
	while temp != 0:
		digit = temp % 10
		if digit % 2:
			oc += digit
		else:
			ec += digit
		temp = temp // 10
	b.append(abs(ec - oc))
diamonds = [0, 2]
temp = 0
for i in range(2, 10 ** 6 + 1):
	temp += b[2 * i - 1] + b[2 * i - 2] - b[i]
	diamonds.append(diamonds[i - 1] + 2 * temp + b[2 * i])
for z in range(int(input())):
	n = int(input())
	print(diamonds[n])


t = int(input().strip())

def findDiamonds(num):
	even = 0
	odd = 0
	while num > 0:
		rem = num % 10
		if rem % 2 == 0:
			even += rem
		else:
			odd += rem
		num //= 10
	return abs(even - odd)
precomputed = [0 for i in range(10 ** 6 + 20)]
prev_row = [0 for i in range(2 * 10 ** 6 + 20)]
prev_row[0] = 2
prev_row_count = 2
first = 0
last = 0
precomputed[1] = 2
for i in range(2, 1000001):
	prev_row_count -= prev_row[first]
	first += 1
	last += 1
	prev_row[last] = findDiamonds(2 * i - 1)
	last += 1
	prev_row[last] = findDiamonds(2 * i)
	prev_row_count += prev_row[last] + prev_row[last - 1]
	precomputed[i] = precomputed[i - 1] + 2 * prev_row_count - prev_row[last]
for i in range(t):
	n = int(input().strip())
	print(precomputed[n])


def digDiff(n):
	odd = 0
	even = 0
	while n > 0:
		dig = n % 10
		if dig & 1 == 0:
			even += dig
		else:
			odd += dig
		n = n // 10
	return abs(even - odd)
dia = [digDiff(i) for i in range(2 * 10 ** 6 + 1)]
dp = [0] * (10 ** 6 + 1)
dp[1] = 2
res = dp[1]
for i in range(2, len(dp)):
	res = res - dia[i] + dia[2 * i - 1] + dia[2 * i]
	dp[i] = dp[i - 1] + 2 * res - dia[2 * i]
for _ in range(int(input())):
	print(dp[int(input())])


def s(k):
	even = 0
	odd = 0
	if k == 0:
		return 0
	while k != 0:
		if k % 10 % 2 == 0:
			even = even + k % 10
		elif k % 10 % 2 == 1:
			odd = odd + k % 10
		k = k // 10
	return abs(odd - even)
a = [0] * (2 * 10 ** 6 + 1)
for i in range(2, 2 * 10 ** 6 + 1):
	if i <= 9:
		a[i] = i
	else:
		a[i] = s(i)
b = [0] * (10 ** 6 + 1)
for j in range(1, 10 ** 6 + 1):
	if i <= 4:
		b[i] = i * i * (i + 1)
	else:
		b[j] = b[j - 1] + b[j - 1] - b[j - 2] - 2 * a[j] + a[2 * j - 2] + 2 * a[2 * j - 1] + a[2 * j]
t = int(input())
for _ in range(t):
	n = int(input())
	print(b[n])


import math
t = int(input().strip())
k = 10 ** 6 + 1
f = [0] * 2 * k
for i in range(10):
	f[i] = i if i % 2 else -i
for i in range(10, 2 * k):
	f[i] = f[i // 10] + f[i % 10]
m = [0] * k
m[1] = 2
m[2] = 12
d = [0] * k
d[2] = 3
for i in range(3, k):
	i2 = i * 2
	d[i] = d[i - 1] - abs(f[i]) + abs(f[i2 - 1]) + abs(f[i2 - 2])
	m[i] = m[i - 1] + 2 * d[i] + abs(f[i2])
for i in range(t):
	n = int(input().strip())
	print(m[n])


from datetime import datetime
x1 = []
x1.append(0)
x3 = []
x3.append(0)
x4 = []
x2 = []
m = 0
sum1 = 0
sum2 = 0
sum4 = 0
for i in range(1, 2000001):
	x = 1 + i
	y = 1000000 + i
	if x % 10 == 0:
		while x % 10 == 0:
			sum1 -= 9
			x = x // 10
		x = x % 10
		sum1 += -(-1) ** (x - 1) * -(x - 1) + (-1) ** x * -x
		m = 0
	else:
		x = x % 10
		sum1 += -m + (-1) ** x * -x
		m = (-1) ** x * -x
	sum2 += abs(sum1)
	x1.append(abs(sum1))
	x3.append(sum2)
x1[-1] = 2
x5 = []
x5.append(0)
z = 0
for i in range(0, 1000000):
	a = (x3[2 * i + 1] - x3[i]) * 2 - x1[2 * i + 1]
	x5.append(a + z)
	z += a
t = int(input())
for i in range(t):
	n = int(input())
	print(x5[n])


t = int(input())
c = []
r = t
while r > 0:
	n = int(input())
	c.append(n)
	r = r - 1
sume = 0
sumo = 0
sumf = 0
p = 0
b = []
b.append(0)
b.append(2)
d = []
d.append(0)
d.append(0)
for i in range(2, 2 * (10 ** 6 + 1) + 1):
	y = i
	while y > 0:
		r = y % 10
		if r % 2 == 0:
			sume = sume + r
		else:
			sumo = sumo + r
		y = y // 10
	d.append(abs(sume - sumo))
	sume = 0
	sumo = 0
x = d[3]
r = 0
for i in range(2, 10 ** 6 + 1):
	r = b[i - 1] + 2 * x + d[2 * i]
	b.append(r)
	x = x + d[2 * i] + d[2 * i + 1] - d[i + 1]
for j in range(t):
	print(b[c[j]])


a = [0] * 1000001
b = [0] * 2000000
c = [0] * 2000000
for i in range(9, 2 * 1000000):
	ev = 0
	od = 0
	su = 0
	qr = i + 1
	while qr >= 10:
		x = qr % 10
		if x % 2 == 0:
			ev = ev + x
		else:
			od = od + x
		qr = qr // 10
	if qr % 2 == 0:
		ev = ev + qr
	else:
		od = od + qr
	su = abs(ev - od)
	b[i] = su
c[9] = b[9]
for i in range(10, 2 * 1000000):
	c[i] = c[i - 1] + b[i]
a[1] = 2
a[2] = 12
a[3] = 36
a[4] = 80
a[5] = 141
a[6] = 196
a[7] = 249
a[8] = 306
a[9] = 373
for i in range(10, 1000000):
	a[i] = a[i - 1] + 2 * (c[2 * i - 2] - c[i - 1]) + b[2 * i - 1]
t = int(input())
for i in range(t):
	n = int(input())
	print(a[n])


mx = 10 ** 6
b = [None, None]
for n in range(2, mx * 2 + 1):
	a = [0, 0]
	while n > 0:
		d = n % 10
		a[d % 2] += d
		n = n // 10
	b.append(abs(a[0] - a[1]))
r = [None, 2, 12]
addend = 10
for n in range(3, mx + 1):
	addend -= 2 * b[n]
	addend += b[2 * n] + 2 * b[2 * n - 1] + b[2 * n - 2]
	r.append(r[-1] + addend)
for t in range(int(input())):
	print(r[int(input())])


l = [0]
for i in range(1, 2000001):
	if i < 10:
		if i % 2 == 0:
			l.append(i)
		else:
			l.append(-i)
	elif int(str(i)[0]) % 2 == 0:
		l.append(int(str(i)[0]) + l[int(str(i)[1:])])
	else:
		l.append(l[int(str(i)[1:])] - int(str(i)[0]))
for i in range(1, 2000001):
	l[i] = abs(l[i])
ansl = [0, 2, 12]
x = 10
for n in range(3, 1000001):
	x = x - 2 * l[n] + l[2 * n - 2] + 2 * l[2 * n - 1] + l[2 * n]
	ansl.append(ansl[n - 1] + x)
t = int(input())
for j in range(t):
	n = int(input())
	print(ansl[n])


l = []
c = []
l.append(0)
l.append(-1)
k = 4
pu = 0
s = 0
c.append(0)
c.append(2)
c.append(12)
c.append(36)
for i in range(2, 2 * 1000000 + 1):
	f = 0
	if i < 10:
		if i % 2 == 0:
			l.append(i)
		else:
			l.append(-i)
	else:
		pi = i // 10
		if i % 2 == 0:
			ele = l[pi] + i % 10
		else:
			ele = l[pi] - i % 10
		l.append(ele)
	if i % 2 == 0 and i >= 8:
		c.append(c[i // 2 - 1] + 2 * s + abs(l[i]))
		f = 1
		if i == 8:
			pu = 5
	if i > 4:
		s += abs(l[i])
		if f == 1:
			s = s - abs(l[pu])
			pu = pu + 1
			f = 0
for i in range(int(input())):
	p = int(input())
	print(c[p])


dic = {'0': 0, '1': 1, '2': -2, '3': 3, '4': -4, '5': 5, '6': -6, '7': 7, '8': -8, '9': 9}
result = {1: 2, 2: 10}

def compute(string):
	count = 0
	for x in string:
		count += dic[x]
	return abs(count)
for i in range(3, 10 ** 6 + 1):
	beta = 2 * i - 2
	gama = 2 * i - 1
	delta = 2 * i
	alpha = i
	beta = compute(str(beta))
	alpha = 2 * compute(str(alpha))
	gama = 2 * compute(str(gama))
	delta = compute(str(delta))
	result[i] = result[i - 1] + beta + gama + delta - alpha
for i in result:
	if i - 1 in result:
		result[i] = result[i] + result[i - 1]
t = int(input())
for i in range(t):
	n = int(input())
	print(result[n])


def reduce(n):
	even = 0
	odd = 0
	while n > 0:
		r = n % 10
		if r % 2 == 0:
			even += r
		else:
			odd += r
		n = int(n / 10)
	return abs(even - odd)
m = 10 ** 6
act = [0]
sum_act = [0]
for i in range(1, 2 * m + 1):
	act.append(reduce(i))
	sum_act.append(act[-1] + sum_act[-1])
mem = [0]
for i in range(m):
	mem.append(mem[-1] + 2 * (sum_act[2 * i + 1] - sum_act[i + 1]) + act[2 * i + 2])
for t in range(int(input())):
	n = int(input())
	ans = mem[n]
	print(ans)


ans = [0] * 2000002
ans[0] = 0
for i in range(1, 2000002):
	x = i
	ec = 0
	oc = 0
	while x > 0:
		j = x % 10
		if j % 2 == 0:
			ec = ec + j
		else:
			oc = oc + j
		x = x // 10
	ans[i] = ans[i - 1] + abs(ec - oc)
real = [0] * 1000002
real[0] = 0
real[1] = 2
for i in range(2, 1000001):
	x = ans[2 * i - 1] - ans[i]
	real[i] = real[i - 1] + 2 * x + ans[2 * i] - ans[2 * i - 1]
t = int(input())
for i in range(t):
	n = int(input())
	print(real[n])


t = int(input())
room_list = []
inp = []
for i in range(t):
	n = int(input())
	inp.append(n)
max_inp = max(inp) + 1
max_rno = 2 * max_inp + 1
for room_no in range(max_rno):
	even = 0
	odd = 0
	while room_no > 0:
		l = room_no % 10
		if l % 2 == 0:
			even += l
		else:
			odd += l
		room_no //= 10
	diamond_count = abs(odd - even)
	room_list.append(diamond_count)
dim_list = [0, 2, 12]
a = 3
for dim in range(3, max_inp):
	stop = dim * 2
	a -= room_list[dim]
	a += room_list[2 * (dim - 1)]
	a += room_list[2 * dim - 1]
	b = a * 2
	b += room_list[stop]
	b += dim_list[-1]
	dim_list.append(b)
for i in range(t):
	print(dim_list[inp[i]])


def dig_diff(n):
	s1 = 0
	s2 = 0
	while n > 0:
		if n % 10 % 2 == 0:
			s1 += n % 10
		else:
			s2 += n % 10
		n //= 10
	return abs(s1 - s2)
lis_dice = [0]
for i in range(1, 2000001):
	lis_dice.append(dig_diff(i) + lis_dice[i - 1])
vals = [0]
for i in range(1, 1000001):
	temp = vals[i - 1]
	temp += lis_dice[i + i] + lis_dice[i + i - 1] - 2 * lis_dice[i]
	vals.append(temp)
n = int(input())
for i in range(n):
	inp = int(input())
	print(vals[inp])


def eval(n):
	ret = 0
	while n:
		no = n % 10
		ret = ret - no if no % 2 else ret + no
		n //= 10
	return abs(ret)
prsum = [0, 0]
for no in range(2, 2000001):
	prsum.append(prsum[-1] + eval(no))
ans = [0, 2]
for no in range(2, 1000001):
	ans.append(ans[-1] + 2 * (prsum[2 * no] - prsum[no]) - eval(2 * no))
for _ in range(int(input().strip())):
	N = int(input().strip())
	print(ans[N])


t = int(input())
c = [-1, -1, 2]
for p in range(3, 2000001):
	c1 = 0
	c2 = 0
	y = p
	while y != 0:
		r = y % 10
		y = y // 10
		if r % 2 == 0:
			c1 = c1 + r
		else:
			c2 = c2 + r
	x = abs(c1 - c2)
	c.append(c[p - 1] + x)
a = [0, 2]
for p in range(2, 1000001):
	x = a[p - 1] + c[2 * p - 1] - 2 * c[p] + c[2 * p]
	a.append(x)
for k in range(t):
	n = int(input())
	print(a[n])


def diamond(k):
	even = odd = 0
	while k > 0:
		x = k % 10
		k //= 10
		if x % 2 == 0:
			even += x
		else:
			odd += x
	return abs(even - odd)
l = [0, 0]
for j in range(2, 2000001):
	l.append(diamond(j))
t = [0, 2, 12]
sum1 = l[3]
for j in range(3, 1000001):
	sum2 = t[j - 1]
	p = 2 * j
	sum1 += l[p - 1] + l[p - 2] - l[j]
	sum2 += 2 * sum1
	sum2 += l[2 * j]
	t.append(sum2)
x = int(input())
for k in range(x):
	n = int(input())
	print(t[n])


T = int(input().strip())
(ans, TD) = ([(0, 0, 0, 0)], [0, 2])
for i in range(1, 10):
	even = 0 if i & 1 else i
	odd = 0 if even else i
	ans.append((even, odd, i, i + ans[i - 1][3]))
for i in range(10, 2 * 1000000 + 2):
	(j, k) = divmod(i, 10)
	even = ans[j][0] + ans[k][0]
	odd = ans[j][1] + ans[k][1]
	diff = abs(even - odd)
	ans.append((even, odd, diff, diff + ans[i - 1][3]))
for i in range(2, 1000001):
	TD.append(TD[i - 1] + ans[2 * i][2] + 2 * (ans[2 * i - 1][3] - ans[i][3]))
for _ in range(T):
	print(TD[int(input().strip())])


from math import *

def calc(n):
	(tmp, i, p) = (n, 0, 0)
	while tmp > 0:
		C = tmp % 10
		tmp //= 10
		if C % 2 == 0:
			p += C
		else:
			i += C
	return int(fabs(i - p))
f = [0, 1]
pref_sum = [0, 1]
dimond = [0, 2]
for i in range(2, 2000003):
	f.append(calc(i))
	pref_sum.append(pref_sum[i - 1] + f[i])
for i in range(2, 1000002):
	dimond.append(dimond[i - 1] + 2 * (pref_sum[2 * i] - pref_sum[i]) - f[2 * i])
T = int(input())
for _ in range(T):
	print(dimond[int(input())])


L = []
for _ in range(int(input())):
	N = int(input())
	L.append(N)
MAX_N = max(L)
Table = [0, 0]
CumTable = [0, 0]
for i in range(2, 2 * MAX_N + 1):
	num = i
	even_sum = 0
	odd_sum = 0
	while num:
		digit = num % 10
		num = num // 10
		if digit % 2 == 0:
			even_sum += digit
		else:
			odd_sum += digit
	diff = int(abs(even_sum - odd_sum))
	Table.append(diff)
	CumTable.append(CumTable[-1] + diff)
AnsTable = [0, 2]
for i in range(2, MAX_N + 1):
	AnsTable.append((CumTable[2 * i - 1] - CumTable[i]) * 2 + Table[2 * i] + AnsTable[-1])
for N in L:
	print(AnsTable[N])


def foo(n):
	(e, o) = (0, 0)
	while n > 0:
		r = n % 10
		n = n // 10
		if r & 1:
			o += r
		else:
			e += r
	return abs(e - o)
N = 2000010
n = 1000002
A = [foo(i) for i in range(N)]
S = [0] * N
for i in range(1, N):
	S[i] = S[i - 1] + A[i]
ans = [0] * n
ans[0] = 2
for i in range(1, n):
	ans[i] = ans[i - 1] + 2 * (S[2 + i + i - 1] - S[2 + i - 1]) + S[2 * (i + 1)] - S[2 * (i + 1) - 1]
T = int(input().strip())
for _ in range(T):
	n = int(input().strip())
	print(ans[n - 1])


from itertools import accumulate
N = 2000001

def f(n):
	ans = 0
	while n:
		r = n % 10
		if r & 1:
			ans += r
		else:
			ans -= r
		n //= 10
	return abs(ans)
g = ((x, i * x) for (i, x) in enumerate(map(f, range(1, N))))
l = list(accumulate(g, lambda x, y: (x[0] + y[0], x[1] + y[1])))
t = int(input())
for _ in range(t):
	n = int(input())
	(l1, l2) = (l[n], l[2 * n - 1])
	print(2 * (l1[1] + n * (l2[0] - l1[0])) - l2[1])


def op(x):
	o = 0
	e = 0
	while x > 0:
		if x % 2:
			o += x % 10
		else:
			e += x % 10
		x //= 10
	return abs(o - e)
N = 1000000
d = [0] * (2 * N + 1)
for i in range(1, 2 * N + 1):
	d[i] = op(i) + d[i - 1]
a = [0] * (N + 1)
a[1] = 2
for i in range(2, N + 1):
	a[i] += a[i - 1] + d[2 * i - 1] + d[2 * i] - 2 * d[i]
t = int(input())
for k in range(t):
	print(a[int(input())])


def diamondsInRoom(n):
	(totalOdds, totalEvens) = (0, 0)
	while n != 0:
		if n % 2 == 0:
			totalEvens += n % 10
		else:
			totalOdds += n % 10
		n //= 10
	return abs(totalOdds - totalEvens)
answers = ['*']
roomNumberValues = [diamondsInRoom(n) for n in range(0, 2 * 10 ** 6 + 1)]
totalDiamonds = 0
diamondsThisEdge_last = 0
for N in range(1, 10 ** 6):
	diamondsThisEdge = diamondsThisEdge_last
	diamondsThisEdge -= roomNumberValues[N]
	diamondsThisEdge += roomNumberValues[2 * N - 1]
	diamondsThisEdge += roomNumberValues[2 * N]
	totalDiamonds += 2 * diamondsThisEdge - roomNumberValues[2 * N]
	answers.append(totalDiamonds)
	diamondsThisEdge_last = diamondsThisEdge
T = int(input())
for _ in range(T):
	N = int(input())
	print(answers[N])


def diamonds(n):
	odd = even = 0
	while n > 0:
		if n % 2 == 0:
			even += n % 10
		else:
			odd += n % 10
		n //= 10
	return abs(odd - even)
N = 1000000
t = int(input())
rooms = [0 for i in range(2 * N + 1)]
dp = [0 for i in range(N + 1)]
for i in range(1, 2 * N + 1):
	rooms[i] = rooms[i - 1] + diamonds(i)
for i in range(1, N + 1):
	dp[i] = dp[i - 1] + 2 * (rooms[2 * i] - rooms[i]) - (rooms[2 * i] - rooms[2 * i - 1])
for caseNr in range(t):
	n = int(input())
	print(dp[n])


T = int(input())
d = [-1] * (2 * 10 ** 6 + 1)
D = [-1] * (2 * 10 ** 6 + 1)
_N = [-1] * (10 ** 6 + 1)
_N[1] = 2
_N[2] = 12
d[0] = 0
d[1] = -1
d[2] = 2
d[3] = -3
d[4] = 4
d[5] = -5
d[6] = 6
d[7] = -7
d[8] = 8
d[9] = -9
D[1] = 0
D[2] = 2
D[3] = 5
D[4] = 9
D[5] = 14
D[6] = 20
D[7] = 27
D[8] = 35
D[9] = 44

def diamond(n):
	lastdigit = n % 10
	if lastdigit % 2 == 0:
		d[n] = d[n // 10] + lastdigit
	else:
		d[n] = d[n // 10] - lastdigit
	D[n] = D[n - 1] + abs(d[n])
for k in range(10, 2 * 10 ** 6):
	diamond(k)
for k in range(3, 10 ** 6 + 1):
	_N[k] = _N[k - 1] + 2 * (D[2 * k] - D[k]) - abs(d[2 * k])
for t in range(0, T):
	N = int(input())
	print(_N[N])


NMAX = 10 ** 6

def val(n):
	S = [0, 0]
	while n:
		d = n % 10
		S[d % 2] += d
		n //= 10
	return abs(S[0] - S[1])

def main():
	R = [0]
	P = [0]
	S = [0]
	for i in range(1, NMAX + 1):
		R.append(val(2 * i - 1))
		P.append(P[-1] + R[-1])
		R.append(val(2 * i))
		P.append(P[-1] + R[-1])
		S.append(S[-1] + R[-1] + 2 * (P[-2] - P[-1 - i]))
	T = int(input())
	for _ in range(T):
		N = int(input())
		print(S[N])
main()


import sys
e = [0 if i % 2 else i for i in range(10)]
o = [i if i % 2 else 0 for i in range(10)]
d = [abs(e[i] - o[i]) for i in range(10)]
ex = [0, 2, 10]
ans = [0, 2, 12]

def prec():
	for i in range(10, 2000001):
		e.append(e[int(i / 10)] + e[i % 10])
		o.append(o[int(i / 10)] + o[i % 10])
		d.append(abs(e[i] - o[i]))
	for n in range(3, 1000001):
		ext = ex[n - 1] - 2 * d[n] + d[2 * (n - 1)] + 2 * d[2 * n - 1] + d[2 * n]
		ex.append(ext)
		ans.append(ans[n - 1] + ext)
prec()

def calc(n):
	ans = 0
	for i in range(2, 2 * n + 1):
		if i > n + 1:
			m = 2 * n - i + 1
		else:
			m = i - 1
		ans += m * d[i]
	return ans
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	print(ans[n])


import numpy as np

def diamonds(k):
	ret = np.zeros(k, dtype=np.int64)
	idx = np.arange(k, dtype=np.int64)
	vals = np.array([j if j & 1 else -j for j in range(10)])
	t = 1
	while t < k:
		i0 = idx // t % 10
		ret += vals[i0]
		t *= 10
	return np.abs(ret)
DD = diamonds(10 ** 6 * 2 + 100)[2:]
D0 = np.cumsum(DD)
D1 = np.cumsum(D0)

def solve(n):
	if n == 1:
		return 2
	n -= 1
	ret = D1[2 * n] - 2 * D1[n - 1]
	return ret
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	n = int(f.readline())
	print(solve(n))


def count(n):
	(c0, c1) = (0, 0)
	while n > 0:
		if n % 2 == 0:
			c0 += n % 10
		else:
			c1 += n % 10
		n //= 10
	return abs(c0 - c1)
N = 1000000
cc = [count(n) for n in range(N + N + 1)]
ss = [0 for n in range(N + N + 1)]
for n in range(1, N + N + 1):
	ss[n] = ss[n - 1] + cc[n]
dd = [0 for n in range(N + 1)]
for n in range(1, N + 1):
	dd[n] = dd[n - 1] + (ss[n + n] - ss[n]) * 2 - cc[n + n]
print(*(dd[int(input())] for _ in range(int(input()))), sep='\n')


from sys import stdin
from bisect import bisect_left, bisect_right
input = stdin.readline
MAX = int(1000000.0) + 1
val = [0] * (MAX << 1)
ans = [0] * MAX

def digit_sum(num):
	(e, o) = (0, 0)
	while num:
		(d, num) = (num % 10, num // 10)
		(e, o) = (e, o + d) if d % 2 else (e + d, o)
	return abs(e - o)
for i in range(1, MAX << 1):
	val[i] = val[i - 1] + digit_sum(i)
for i in range(1, MAX):
	ans[i] = ans[i - 1] + val[i << 1] + val[i - 1 << 1 | 1] - (val[i] << 1)
t = int(input().strip())
while t:
	n = int(input().strip())
	print(ans[n])
	t -= 1