Polo, the Penguin, likes numbers. He says that the goodness of a number is itself multiplied by the number of digits in it's decimal representation. For example, the goodness of the integer 474 is 474*3 = 1422.
Help him to count the sum of goodness of all integers from L to R, inclusive. Since the answer can be too large, output it modulo 1,000,000,007 (10^9+7).

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The only line of each test case contains the pair of integers L and R, separated by a single space.

-----Output-----
For each test case, output a single line containing the answer to the corresponding test case.

-----Constraints-----
- 1 ≤ T ≤ 1,000
- 1 ≤ L ≤ R ≤ 1,000,000,000 (10^9)

-----Example-----
Input:
1
9 12

Output:
75

-----Explanation-----
Example case 1. The answer is 9*1 + 10*2 + 11*2 + 12*2 = 75.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
def sumn(a):
	s = a * (a + 1) // 2
	return s
t = [1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000]
m = 1000000007
tc = eval(input())
while tc > 0:
	s1 = input().split(' ')
	a = int(s1[0])
	b = int(s1[1])
	l1 = len(s1[0])
	l2 = len(s1[1])
	sum = 0
	if l1 == l2:
		sum = (sumn(b) - sumn(a - 1)) * l1
	else:
		x = (sumn(t[l1] - 1) - sumn(a - 1)) * l1
		y = (sumn(b) - sumn(t[l2 - 1] - 1)) * l2
		sum = x + y
		for i in range(l1 + 1, l2):
			sum += (sumn(t[i] - 1) - sumn(t[i - 1] - 1)) * i
	sum = sum % m % m
	print(int(sum))
	tc -= 1


t = int(input())
for i in range(t):
	(l, r) = map(int, input().split())
	start = len(str(l))
	end = len(str(r))
	if end > start:
		end_start = int(str('9' * start))
		sum_start = (end_start + l) * start * (end_start - l + 1) // 2
	else:
		sum_start = (l + r) * start * (r - l + 1) // 2
	sum = 0
	for j in range(start + 1, end):
		sum += (10 ** (j - 1) + int(str('9' * j))) * j * (int(str('9' * j)) - 10 ** (j - 1) + 1) // 2
	if end > start:
		end = len(str(r))
		end__start = int(str(10 ** (end - 1)))
		sum__start = (end__start + r) * end * (r - end__start + 1) // 2
	else:
		sum__start = 0
	print((sum + sum__start + sum_start) % 1000000007)


def nod(n):
	digs = 0
	while n > 0:
		digs += 1
		n //= 10
	return digs
t = int(input())
mbase = 1000000007
for it in range(t):
	(L, R) = [int(word) for word in input().split()]
	l = nod(L)
	r = nod(R)
	s = 0
	if l == r:
		s = l * (R * (R + 1) - L * (L - 1)) // 2
		s %= mbase
	else:
		tenl = 10 ** l
		s += l * (tenl * (tenl - 1) - L * (L - 1)) // 2
		s %= mbase
		tenrm1 = 10 ** (r - 1)
		s += r * (R * (R + 1) - tenrm1 * (tenrm1 - 1)) // 2
		s %= mbase
		for i in range(l + 1, r):
			teni = 10 ** (i - 1)
			s += 9 * i * teni * (11 * teni - 1) // 2
			s %= mbase
	print(s)


from sys import stdin
from math import sqrt, ceil, log10

def get_sum(a, b, digits):
	sum = (b + a) * (b - a + 1) // 2
	return sum * digits

def solve():
	mod = 10 ** 9 + 7
	thehighlimiter = {i: 10 ** i - 1 for i in range(12)}
	thelowlimiter = {i: 10 ** i for i in range(12)}
	for _ in range(int(input())):
		(l, r) = map(int, stdin.readline().strip().split())
		low = len(str(l))
		high = len(str(r))
		ans = 0
		if low == high:
			ans = get_sum(l, r, low)
		else:
			ans += get_sum(l, 10 ** low - 1, low)
			ans += get_sum(10 ** (high - 1), r, high)
			for i in range(low + 1, high):
				ans += get_sum(10 ** (i - 1), 10 ** i - 1, i)
		print(ans % mod)

def __starting_point():
	solve()
__starting_point()


try:
	t = int(input())
	for i in range(t):
		(l, r) = map(str, input().split())
		k = len(l)
		j = len(r)
		sum = 0
		if j > k:
			for i in range(k, j):
				s = 10 ** i - int(l)
				sum = sum + (s * int(l) + (s - 1) * s // 2) * i
				l = 10 ** i
			a = ((int(r) - int(l) + 1) * l + (int(r) - int(l) + 1) * (int(r) - int(l)) // 2) * j
			sum = sum + a
			print(sum % (10 ** 9 + 7))
		elif j == k:
			sum = ((int(r) - int(l) + 1) * int(l) + (int(r) - int(l)) * (int(r) - int(l) + 1) // 2) * j
			print(sum % (10 ** 9 + 7))
except:
	pass


def sumn(a1, b1):
	b = max(a1, b1)
	a = min(a1, b1)
	s = (a + b) * (b - a + 1) // 2
	return s
m = 1000000007
tc = eval(input())
while tc > 0:
	s1 = input().split(' ')
	a = int(s1[0])
	b = int(s1[1])
	sum = 0
	f = a
	while f <= b:
		ln = len(str(f))
		s = min(10 ** ln - 1, b)
		sum += sumn(s, f) % m * ln % m
		f = s + 1
	sum = sum % m % m
	print(int(sum))
	tc -= 1


t = int(input())
mod = 1000000007

def get_sum(a, b, digits):
	sum = (b + a) * (b - a + 1) // 2
	return sum * digits
for _ in range(t):
	(l, r) = [int(x) for x in input().split()]
	l_digits = len(str(l))
	r_digits = len(str(r))
	ans = 0
	if l_digits == r_digits:
		ans = get_sum(l, r, l_digits)
	else:
		ans += get_sum(l, 10 ** l_digits - 1, l_digits)
		ans += get_sum(10 ** (r_digits - 1), r, r_digits)
		for i in range(l_digits + 1, r_digits):
			ans += get_sum(10 ** (i - 1), 10 ** i - 1, i)
	print(ans % mod)


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)
	return r1 if r1 == r2 else None
MODULO = 1000000007

def alg(L, R):
	res = 0
	for n in range(L, R + 1):
		res += len(str(n)) * n
		res %= MODULO
	return res

def alg2(L, R):
	res = 0
	subL = L

	def sub_alg(left, right, nb_dig):
		sum_ = (right - left + 1) * (right + left) // 2
		return sum_ * nb_dig % MODULO
	while True:
		digL = len(str(subL))
		digR = len(str(R))
		if digL == digR:
			res += sub_alg(subL, R, digL)
			break
		subR = int('9' * digL)
		res += sub_alg(subL, subR, digL)
		subL = subR + 1
	return res % MODULO

def main():
	data = sys.stdin
	nb = int(data.readline())
	for icase in range(nb):
		(L, R) = list(map(int, data.readline().split()))
		res = alg2(L, R)
		print(res)
main()


def len(n):
	x = 0
	while n > 0:
		x += 1
		n = n // 10
	return x
e = 10 ** 9 + 7
t = int(input())
f = [0]
a = 9
b = 1
for i in range(10):
	x = (2 * b + a - 1) % e
	x = x * a % e
	y = pow(2, e - 2, e)
	x = x * y % e
	x = x * (i + 1) % e
	x = (x + f[-1]) % e
	b *= 10
	a *= 10
	f.append(x)

def ans(n):
	if n == 0:
		return 0
	x = len(n)
	y = f[x - 1]
	a = pow(10, x - 1, e)
	b = (n + a) * (n - a + 1) % e
	b = b * pow(2, e - 2, e) % e
	b = b * x % e
	return (b + y) % e
for _ in range(t):
	(a, b) = map(int, input().split())
	b = ans(b)
	a = ans(a - 1)
	print((b - a) % e)


highs = {i: 10 ** (i - 1) for i in range(12)}
lows = {i: 10 ** i for i in range(12)}
mod = 1000000007

def solve():
	(l, r) = input().split()
	ll = len(l)
	rl = len(r)
	l = int(l)
	r = int(r)
	if ll == rl:
		return (l + r) * (r - l + 1) * ll // 2 % mod
	r1 = 10 ** ll - 1
	r2 = 10 ** (rl - 1)
	ans = ((l + r1) * (r1 - l + 1) * ll // 2 + (r2 + r) * (r - r2 + 1) * rl // 2) % mod
	for i in range(ll + 1, rl):
		a = 10 ** (i - 1)
		b = 10 ** i - 1
		ans += (a + b) * (b - a + 1) * i // 2 % mod
	return ans % mod
for _ in range(int(input())):
	print(solve())


mod = 1000000007

def getAns(R):
	if R < 10:
		return R * (R + 1) // 2
	ans = 45
	p = 100
	c = 2
	while R >= p - 1:
		A = p // 10
		B = p - 1
		curAns = B * (B + 1) // 2 % mod
		curAns -= A * (A - 1) // 2 % mod
		curAns = (curAns + mod) % mod
		ans = (ans + c * curAns) % mod
		c += 1
		p *= 10
	p //= 10
	curAns = R * (R + 1) // 2 % mod
	curAns -= p * (p - 1) // 2 % mod
	ans = (ans + curAns * c) % mod
	return ans
for tc in range(int(input())):
	(L, R) = map(int, input().strip().split())
	print((getAns(R) - getAns(L - 1) + mod) % mod)


a = int(input())
for i in range(a):
	(L, R) = map(int, input().split())
	m = len(str(L))
	n = len(str(R))
	if m == n:
		x = (R - L + 1) * (L + R) // 2
		y = x * n
		print(y % (10 ** 9 + 7))
	else:
		x = 0
		for j in range(m + 1, n):
			x += 9 * 10 ** (j - 1) // 2 * (11 * 10 ** (j - 1) - 1) * j
		p = int('9' * m)
		x += (p - L + 1) * (L + p) // 2 * m
		q = 10 ** (n - 1)
		x += (R - q + 1) * (q + R) // 2 * n
		print(x % (10 ** 9 + 7))


import sys

def SUM(L, R):
	return (L + R) * (R + 1 - L) // 2
T = int(sys.stdin.readline())
Ans = ''
MOD = 1000000007
for t in range(T):
	(L, R) = map(int, sys.stdin.readline().split())
	NL = len(str(L))
	NR = len(str(R))
	if NL == NR:
		Ans += str(SUM(L, R) * NL % MOD) + '\n'
	else:
		ans = 0
		ans += SUM(L, 10 ** NL - 1) * NL % MOD
		ans += SUM(10 ** (NR - 1), R) * NR % MOD
		for i in range(NL + 1, NR):
			ans += SUM(10 ** (i - 1), 10 ** i - 1) * i % MOD
		ans %= MOD
		Ans += str(ans) + '\n'
sys.stdout.write(Ans)


MOD = 10 ** 9 + 7
t = int(input())
for index in range(t):
	inp = input().split()
	l = int(inp[0])
	r = int(inp[1])
	u = l
	result = 0
	while u <= r:
		numOfDigits = len(str(u))
		v = min(10 ** numOfDigits - 1, r)
		result += numOfDigits * (u + v) * (v - u + 1) // 2
		result %= MOD
		u = v + 1
	print(result)


m = 10 ** 9 + 7

def get_sum(a, b, digits):
	sum = (b + a) * (b - a + 1) // 2
	return sum * digits
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	l_digits = len(str(l))
	r_digits = len(str(r))
	if l_digits == r_digits:
		ans = get_sum(l, r, l_digits)
	else:
		ans = get_sum(l, 10 ** l_digits - 1, l_digits) + get_sum(10 ** (r_digits - 1), r, r_digits)
		for i in range(l_digits + 1, r_digits):
			ans += get_sum(10 ** (i - 1), 10 ** i - 1, i)
	print(ans % m)


def li():
	return list(map(int, input().split()))
	return a

def si():
	return input().split()

def ii():
	return int(input())
highs = {i: 10 ** (i - 1) for i in range(12)}
lows = {i: 10 ** i for i in range(12)}
inf = 1000000007
for tastcas in range(int(input())):
	(l, r) = si()
	ll = len(l)
	rl = len(r)
	l = int(l)
	r = int(r)
	if ll == rl:
		ans = (l + r) * (r - l + 1) * ll // 2
	else:
		r1 = 10 ** ll - 1
		r2 = 10 ** (rl - 1)
		ans = ((l + r1) * (r1 - l + 1) * ll // 2 + (r2 + r) * (r - r2 + 1) * rl // 2) % inf
		for i in range(ll + 1, rl):
			a = 10 ** (i - 1)
			b = 10 ** i - 1
			ans += (a + b) * (b - a + 1) * i // 2
			ans %= inf
	print(ans % inf)


def sumf(a):
	s = a * (a + 1) // 2
	return s
t = list()
for i in range(10):
	t.append(10 ** i)
m = 1000000007
tc = eval(input())
while tc > 0:
	s1 = input().split(' ')
	a = int(s1[0])
	b = int(s1[1])
	l1 = len(s1[0])
	l2 = len(s1[1])
	s = 0
	if l1 == l2:
		s = (sumf(b) - sumf(a - 1)) % m * l1
	else:
		x = (sumf(t[l1] - 1) - sumf(a - 1)) % m * l1 % m
		y = (sumf(b) - sumf(t[l2 - 1] - 1)) % m * l2 % m
		s = x + y
		for i in range(l1 + 1, l2):
			s += (sumf(t[i] - 1) - sumf(t[i - 1] - 1)) * i
	print(s % m)
	tc -= 1


from math import log10, ceil, floor
from random import randint

def amountOfDigits(n):
	return floor(log10(n)) + 1

def Triangular(n):
	return n * (n + 1) // 2
MOD = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	(L, R) = [int(x) for x in input().split()]
	fullGroupValues = ['*'] + [(Triangular(10 ** i - 1) - Triangular(10 ** (i - 1) - 1)) * i for i in range(1, 9 + 1)]
	L_length = amountOfDigits(L)
	R_length = amountOfDigits(R)
	totalValue = 0
	if L_length == R_length:
		totalValue += (Triangular(R) - Triangular(L - 1)) * L_length
	else:
		totalValue += (Triangular(10 ** L_length - 1) - Triangular(L - 1)) * L_length
		totalValue += sum(fullGroupValues[L_length + 1:R_length - 1 + 1])
		totalValue += (Triangular(R) - Triangular(10 ** (R_length - 1) - 1)) * R_length
	print(totalValue % MOD)


def main():
	test_case = int(input().strip())
	while test_case > 0:
		(left, right) = map(int, input().strip().split())
		mod_no = 10 ** 9 + 7
		p = 1
		ans = 0
		for i in range(1, 10):
			q = p * 10 - 1
			x = max(p, left)
			y = min(q, right)
			if x <= y:
				x %= mod_no
				y %= mod_no
				r = (y * (y + 1) // 2 - x * (x - 1) // 2) % mod_no
				r = r * i % mod_no
				ans = (ans + r) % mod_no
			p *= 10
		if ans < 0:
			ans += mod_no
		print(ans)
		test_case -= 1
main()


def bsum(x, y):
	return y * (y + 1) // 2 - x * (x - 1) // 2
import math
t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	ldig = int(math.log10(l))
	rdig = int(math.log10(r))
	if ldig == rdig:
		total = bsum(l, r) * (ldig + 1)
	else:
		total = bsum(l, 10 ** (ldig + 1) - 1) * (ldig + 1) % (10 ** 9 + 7) + bsum(10 ** rdig, r) * (rdig + 1) % (10 ** 9 + 7)
		for i in range(ldig + 1, rdig):
			total += bsum(10 ** i, 10 ** (i + 1) - 1) * (i + 1)
			total %= 10 ** 9 + 7
	print(total % (10 ** 9 + 7))


mod = int(1000000000.0 + 7)
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	(ten, lcnt) = (1, 0)
	lt = l
	while lt > 0:
		lcnt += 1
		ten *= 10
		lt //= 10
	rt = r
	rcnt = 0
	while rt > 0:
		rcnt += 1
		rt //= 10
	prev = l - 1
	ans = 0
	while lcnt < rcnt:
		val = (ten - 1) * ten // 2
		val -= prev * (prev + 1) // 2
		val = val % mod * lcnt % mod
		ans = (ans % mod + val % mod) % mod
		lcnt += 1
		prev = ten - 1
		ten *= 10
	val = r * (r + 1) // 2
	val -= prev * (prev + 1) // 2
	val = val % mod * rcnt % mod
	ans = (ans % mod + val % mod) % mod
	print(ans)


m = 1000000007
a = []
b = []
a.append(1)
b.append(9)
for i in range(1, 10):
	a.append(a[i - 1] * 10)
	b.append(10 ** (i + 1) - 1)

def getcount(val):
	s = 0
	while val != 0:
		s += 1
		val //= 10
	return s
for t in range(int(input())):
	temp = list(map(int, input().split()))
	l = temp[0]
	r = temp[1]
	c1 = getcount(l)
	c2 = getcount(r)
	if c1 == c2:
		n = r - l + 1
		x = l * n % m
		y = n * (n - 1) // 2 % m
		z = (x + y) % m
		s = z * c1 % m
		print(s)
		continue
	ans = 0
	n = b[c1 - 1] - l + 1
	x = l * n % m
	y = n * (n - 1) // 2 % m
	z = (x + y) % m
	ans += z * c1 % m
	ans %= m
	i = c1 + 1
	while i < c2:
		n = b[i - 1] - a[i - 1] + 1
		x = a[i - 1] * n % m
		y = n * (n - 1) // 2 % m
		z = (x + y) % m
		ans += z * i % m
		ans %= m
		i += 1
	n = r - a[c2 - 1] + 1
	x = a[c2 - 1] * n % m
	y = n * (n - 1) // 2 % m
	z = (x + y) % m
	ans += z * c2 % m
	ans %= m
	print(ans)