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

Eugene loves sequences, especially arithmetic progressions. One day he was asked to solve a difficult problem.

If a sequence of numbers A_{1}, A_{2}, ... , A_{N} form an arithmetic progression A, he was asked to calculate sum of F(A_{i}), for L ≤ i ≤ R.
F(X) is defined as:

If X < 10 then F(X) = X.

Else F(X) = F(sum_{of}_digits(X)).

Example:

F(1378) = 
F(1+3+7+8) = 
F(19) = 
F(1 + 9) = 
F(10) = 
F(1+0) = 
F(1) = 1

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

The first line of the input contains an integer T denoting the number of test cases.
Each test case is described in one line containing four integers: A_{1} denoting the first element of the arithmetic progression A, D denoting the common difference between successive members of A, and L and R as described in the problem statement.

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

For each test case, output a single line containing one integer denoting sum of F(A_{i}).

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ A_{1} ≤ 10^{9}$
$0 ≤ D ≤ 10^{9}$
$1 ≤ R ≤ 10^{18}$
$1 ≤ L ≤ R$

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

$Subtask 1:  0 ≤ D ≤ 100, 1 ≤ A_{1} ≤ 10^{9}, 1 ≤ R ≤ 100  - 15 points$

$Subtask 2:  0 ≤ D ≤ 10^{9}, 1 ≤ A_{1} ≤ 10^{9}, 1 ≤ R ≤ 10^{6}  - 25 points$

$Subtask 3: Original constraints - 60 points$

----- Sample Input 1 ------ 
2

1 1 1 3

14 7 2 4
----- Sample Output 1 ------ 
6

12
----- explanation 1 ------ 
Example case 1.
A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...}
A1 = 1
A2 = 2
A3 = 3
F(A1) = 1
F(A2) = 2
F(A3) = 3
1+2+3=6

Example case 2.
A = {14, 21, 28, 35, 42, 49, 56, 63, 70, 77,  ...}
A2 = 21
A3 = 28
A4 = 35
F(A2) = 3
F(A3) = 1
F(A4) = 8
3+1+8=12

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
def S(n):
	if n % 9 == 0:
		return 9
	else:
		return n % 9
for _ in range(int(input())):
	(a, d, l, r) = map(int, input().split())
	e = a
	s = 0
	for i in range(9):
		s += S(e)
		e += d
	t = r - l + 1
	u = t // 9
	l2 = u * 9
	l1 = u * s
	v = t % 9
	e = a + (l + l2 - 1) * d
	s1 = 0
	for i in range(v):
		s1 += S(e)
		e += d
	ans = s1 + l1
	print(ans)


t = int(input())
for j in range(0, t):
	ln = input().split()
	a = int(ln[0])
	d = int(ln[1])
	l = int(ln[2])
	r = int(ln[3])
	x = a + (l - 1) * d
	p = 100
	while p >= 10:
		p = 0
		while x > 0:
			p = p + x % 10
			x = x // 10
		x = p
	q = 100
	x = d
	while q >= 10:
		q = 0
		while x > 0:
			q = q + x % 10
			x = x // 10
		x = q
	v = [0] * 100
	v[0] = p
	for i in range(1, 9):
		x = p + q
		if x >= 10:
			y = x % 10
			x = x // 10
			y = y + x
		else:
			y = x
		p = y
		v[i] = p + v[i - 1]
	n = (r - l + 1) // 9
	s = n * v[8]
	n = (r - l + 1) % 9
	s += v[n - 1]
	print(s)


def sum_digits(n):
	if n < 10:
		return n
	else:
		count = 0
		while n:
			count += n % 10
			n = n // 10
		return sum_digits(count)
for _ in range(0, int(input())):
	(a, d, l, r) = map(int, input().split())
	ap = []
	for i in range(1, 10):
		x = a + (i - 1) * d
		ap.append(sum_digits(x))
	sr = sum((x for x in ap))
	y = (r - l + 1) // 9
	res = y * sr
	l = l + 9 * y
	while l <= r:
		res += ap[(l - 1) % 9]
		l = l + 1
	print(res)


for i in range(int(input())):
	(A, D, L, R) = map(int, input().split())
	(ans, val) = (0, 0)
	D %= 9
	A = (A + (L - 1) * D) % 9
	if not A:
		A = 9
	if not D:
		D = 9
	R = R - L
	for j in range(R % 9 + 1):
		if not (A + j * D) % 9:
			ans += 9
		else:
			ans += (A + j * D) % 9
	for j in range(9):
		if not (A + j * D) % 9:
			val += 9
		else:
			val += (A + j * D) % 9
	ans += R // 9 * val
	print(ans)


def SumOfDigits(x):
	if x == 0:
		return 0
	sum1 = 0
	while x > 0:
		sum1 += x % 10
		x = x // 10
	if sum1 > 9:
		sum1 = SumOfDigits(sum1)
		return sum1
	else:
		return sum1
t = int(input())
for i in range(1, t + 1):
	(a1, d, l, r) = list(map(int, input().split()))
	tot = 0
	if d == 0:
		if a1 < 10:
			tot = a1 * (r - l + 1)
		else:
			tot = SumOfDigits(a1) * (r - l + 1)
	else:
		tot = 0
		ll = l
		L = a1 + (l - 1) * d
		R = a1 + (r - 1) * d
		while L < 10 and ll <= r:
			tot += L
			L += d
			ll += 1
		w = SumOfDigits(d)
		if w % 9 == 0:
			diff = SumOfDigits(L)
			tot += (r - ll + 1) * diff
		elif w % 3 == 0:
			if SumOfDigits(L) % 3 == 1:
				tot += (r - ll + 1) // 3 * 12
			elif SumOfDigits(L) % 3 == 2:
				tot += (r - ll + 1) // 3 * 15
			else:
				tot += (r - ll + 1) // 3 * 18
			e = (r - ll + 1) % 3
			if e > 0:
				diff = SumOfDigits(L)
				tot += diff
				e -= 1
			while e > 0:
				diff = SumOfDigits(diff + w)
				tot += diff
				e -= 1
		else:
			tot += (r - ll + 1) // 9 * 45
			e = (r - ll + 1) % 9
			if e > 0:
				diff = SumOfDigits(L)
				tot += diff
				e -= 1
			while e > 0:
				diff = SumOfDigits(diff + w)
				tot += diff
				e -= 1
	print(tot)


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

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

def ii():
	return int(input())

def ip():
	return input()

def reduceTo1(n):
	if len(str(n)) == 1:
		return n
	else:
		sum = 0
		for i in str(n):
			sum += int(i)
		return reduceTo1(sum)
for tastcas in range(int(input())):
	(a1, d, l, r) = li()
	al = a1 + (l - 1) * d
	nos = [reduceTo1(al)]
	t = reduceTo1(nos[-1] + d)
	while t != nos[0]:
		nos.append(t)
		t = reduceTo1(nos[-1] + d)
	length = len(nos)
	rng = r - l + 1
	s1 = rng // length
	ans = s1 * sum(nos)
	for i in range(rng - s1 * length):
		ans += nos[i]
	print(ans)


import sys
t = int(input())

def digit_sum(num):
	sm = sum((int(c) for c in str(num)))
	sm = sum((int(c) for c in str(sm)))
	sm = sum((int(c) for c in str(sm)))
	return sm

def digitsum(x):
	if x % 9 == 0:
		x = 9
	else:
		x = x % 9
	return x

def digitsum2(n):
	ans = 0
	while n > 0:
		tmp = int(n % 1000000000)
		while tmp > 0:
			ans += tmp % 10
			tmp = tmp // 10
			if ans > 9:
				ans = ans % 10 + 1
		n = n // 1000000000
	return ans
while t:
	t = t - 1
	(a, d, lb, ub) = [int(x) for x in input().split()]
	(repeat_factor, x) = (9, 0)
	(n, beg, pattern_sum, end) = (ub - lb + 1, a + (lb - 1) * d, 0, a + (ub - 1) * d)
	repeat_factor = min(n, repeat_factor)
	pattern = [0] * repeat_factor
	i = beg
	pattern[x] = digitsum(i)
	x = x + 1
	i += d
	while x < repeat_factor:
		pattern[x] = digitsum(i)
		pattern[x] += pattern[x - 1]
		x = x + 1
		i += d
	pattern_sum = pattern[min(repeat_factor, n) - 1]
	(mul, rem) = (n // repeat_factor, n % repeat_factor)
	if mul > 1:
		pattern_sum *= mul
	if rem > 0 and n > 9:
		pattern_sum += pattern[rem - 1]
	print(pattern_sum)


import math
for T in range(0, int(input())):
	(A, D, L, R) = map(int, input().split())
	Arr = []
	sum = int(0)
	A = int(A) % 9
	D = int(D) % 9
	A = int(A + (L - 1) * D)
	for i in range(0, 9):
		if A % 9 is 0:
			Arr.append(int(9))
		else:
			Arr.append(int(A % 9))
		A = A + D
	K = int(R - L + 1)
	of = int(K / 9)
	pf = int(K % 9)
	sum = int(0)
	for i in range(0, 9):
		sum = sum + of * Arr[i]
	for i in range(0, pf):
		sum = sum + Arr[i]
	print(int(sum))


T = int(input())
while T > 0:
	inp = input()
	(a, d, l, r) = list(map(int, inp.split()))
	sums = [0 for _ in range(10)]
	temp = a + (l - 1) * d
	lim = r - l + 1
	rem = lim % 9
	sums[1] = 1 + (temp - 1) % 9
	for k in range(2, 10):
		temp += d
		sums[k] = sums[k - 1] + (1 + (temp - 1) % 9)
	if lim == rem:
		print(sums[rem])
	else:
		sums[9] *= lim // 9
		sums[9] += sums[rem]
		print(sums[9])
	T -= 1


t = int(input())
for j in range(0, t):
	ln = input().split()
	a = int(ln[0])
	d = int(ln[1])
	l = int(ln[2])
	r = int(ln[3])
	x = a + (l - 1) * d
	st = 999
	while st >= 10:
		st = 0
		while x > 0:
			st = st + x % 10
			x = x // 10
		x = st
	dt = 999
	x = d
	while dt >= 10:
		dt = 0
		while x > 0:
			dt = dt + x % 10
			x = x // 10
		x = dt
	arr = [0] * 100
	arr[0] = st
	for i in range(1, 9):
		x = st + dt
		if x >= 10:
			y = x % 10
			x = x // 10
			y = y + x
		else:
			y = x
		st = y
		arr[i] = st + arr[i - 1]
	n = (r - l + 1) // 9
	ans = n * arr[8]
	n = (r - l + 1) % 9
	ans += arr[n - 1]
	print(ans)


__author__ = 'masterchief'

def solve():
	num_test = int(input())
	for i in range(num_test):
		test_case()

def test_case():
	(a_1, d, l, r) = [int(i) for i in input().split()]
	a_L = f(a_1 + (l - 1) * d)
	d = f(d)
	s2 = 0
	for i in range((r - l + 1) % 9):
		a_temp = f(a_L + i * d)
		s2 += a_temp
	terms_9 = (r - l + 1) // 9
	if terms_9 != 0:
		for i in range(9):
			a_temp = terms_9 * f(a_L + i * d)
			s2 += a_temp
	print(s2)

def f(num):
	return (num - 1) % 9 + 1
solve()


c = 1
cases = int(input())

def break_down(a):
	if a <= 9:
		return a
	else:
		sum = 0
		for i in str(a):
			sum += int(i)
		return break_down(sum)
while c <= cases:
	[a, d, l, r] = [int(i) for i in input().split(' ')]
	ds = []
	for i in range(0, 9):
		ds.append(break_down(a))
		a += d
	ds = ds[l % 9 - 1:] + ds[:l % 9 - 1]
	ans = (r - l + 1) // 9 * sum(ds) + sum(ds[:(r - l + 1) % 9])
	print(ans)
	c = c + 1


def F(x):
	return (x - 1) % 9 + 1
for _ in range(int(input())):
	(A, D, L, R) = map(int, input().split())
	L = L - 1
	R = R - 1
	sum_per9 = 0
	for i in range(0, 9):
		sum_per9 += F(A + D * i)
	ans = 0
	while (R - L + 1) % 9 != 0:
		ans += F(A + D * R)
		R -= 1
	ans += sum_per9 * (R - L + 1) // 9
	print(ans)


t = int(input())
for z in range(t):
	(a, d, l, r) = map(int, input().split())
	(s, len1) = (0, r - l + 1)
	h = [0] * 15
	cf = []
	for i in range(l, r + 1):
		term = a + (i - 1) * d
		val = 0
		if term % 9 == 0:
			val = 9
		else:
			val = term % 9
		if h[val] == 1:
			break
		cf.append(val)
		h[val] = 1
	for i in range(1, len(cf)):
		cf[i] += cf[i - 1]
	len2 = len(cf)
	last_val = cf[len2 - 1]
	s = s + len1 // len2 * last_val
	if len1 % len2 is not 0:
		s = s + cf[len1 % len2 - 1]
	print(int(s))


T = int(input())
while T:
	(A, D, L, R) = map(int, input().split())
	li = []
	a = A + (L - 1) * D
	k = a % 9
	if k:
		li.append(k)
	else:
		li.append(9)
	ans = 0
	i = 2
	while i <= 9:
		k = k + D
		k = k % 9
		if k:
			li.append(k)
		else:
			li.append(9)
		i = i + 1
	lisum = sum(li)
	ans = lisum * int((R - L + 1) / 9)
	x = int((R - L + 1) % 9)
	for i in range(1, x + 1):
		ans = ans + li[i - 1]
	print(ans)
	T = T - 1


def reduceToInt(num):
	while num > 9:
		res = 0
		while num > 0:
			res += num % 10
			num //= 10
		num = res
	return num
T = int(input())
for _ in range(T):
	(A, D, L, R) = map(int, input().split())
	st = A + (L - 1) * D
	arr = [reduceToInt(st)]
	while True:
		next = reduceToInt(arr[-1] + D)
		if next in arr:
			break
		else:
			arr.append(next)
	totalNumbers = R - L + 1
	sm = totalNumbers // len(arr) * sum(arr)
	for i in range(totalNumbers % len(arr)):
		st = reduceToInt(st)
		sm += st
		st += D
	print(sm)


import sys
import math

def nextLine():
	return sys.stdin.readline()

def digitalRoot(x):
	return 1 + (x - 1) % 9

def calculateSumForRange(L, R, A, D, sum9):
	first9 = 0
	n = R - L + 1
	if sum9 is None:
		first9 = sumOfFirst(A, D, 9)
	else:
		first9 = sum9
	if n % 9 == 0:
		return int(n / 9) * first9
	elif n / 9 < 1:
		return sumOfFirst(A + (L - 1) * D, D, n)
	else:
		m = R - n % 9
		return calculateSumForRange(L, m, A, D, first9) + calculateSumForRange(m + 1, R, A, D, first9)

def sumOfFirst(A, D, num):
	sum = 0
	for i in range(0, num):
		sum += digitalRoot(A + i * D)
	return sum
testCases = int(nextLine())
for i in range(0, testCases):
	line = nextLine()
	(A1, D, L, R) = tuple((int(x) for x in line.split(' ')))
	print(calculateSumForRange(L, R, A1, D, None))


def f(x):
	if int(x) < 10:
		return x
	else:
		s = 0
		x = str(x)
		for i in x:
			s += int(i)
		return f(s)
t = int(input())
for _ in range(t):
	(a, d, l, r) = list(map(int, input().strip().split()))
	a = f(a)
	d = f(d)
	s = 0
	seen = []
	fa = f(a)
	while fa not in seen:
		seen.append(fa)
		a += d
		fa = f(a)
	x = (l % len(seen) - 1) % len(seen)
	n = r - l + 1
	s = sum(seen)
	tot = s * (n // len(seen))
	for i in range(n % len(seen)):
		tot += seen[(i + x) % len(seen)]
	print(tot)


import sys

def F(x):
	return (x - 1) % 9 + 1
T = int(sys.stdin.readline())
for t in range(T):
	inp = sys.stdin.readline().split()
	(A, D, L, R) = (int(inp[0]), int(inp[1]), int(inp[2]) - 1, int(inp[3]) - 1)
	sum_per9 = 0
	for i in range(1, 10):
		sum_per9 += F(A + D * i)
	ans = 0
	while (R - L + 1) % 9 != 0:
		ans += F(A + D * R)
		R -= 1
	ans += sum_per9 * (R - L + 1) // 9
	sys.stdout.write(str(ans) + '\n')


import sys

def F(x):
	return (x - 1) % 9 + 1
T = int(input())
for t in range(T):
	inp = input().split()
	(A, D, L, R) = (int(inp[0]), int(inp[1]), int(inp[2]) - 1, int(inp[3]) - 1)
	sum_per9 = 0
	for i in range(1, 10):
		sum_per9 += F(A + D * i)
	ans = 0
	while (R - L + 1) % 9 != 0:
		ans += F(A + D * R)
		R -= 1
	ans += sum_per9 * (R - L + 1) // 9
	print(ans)


import sys
from array import array
input = sys.stdin.readline
out = array('q')
for _ in range(int(input())):
	(a1, d, l, r) = map(int, input().split())
	vis = array('b')
	(cur, sum_, period) = ((a1 - 1) % 9 + 1, 0, 0)
	while cur not in vis:
		vis.append(cur)
		period += 1
		sum_ += cur
		a1 += d
		cur = (a1 - 1) % 9 + 1
	(divr, modr) = divmod(r, period)
	(divl, modl) = divmod(l - 1, period)
	out.append(sum_ * divr + sum(vis[:modr]) - sum_ * divl - sum(vis[:modl]))
print('\n'.join(map(str, out)))


def F(x):
	return (x - 1) % 9 + 1
t1 = int(input())
for t in range(t1):
	(A, D, L, R) = map(int, input().split())
	L = L - 1
	R = R - 1
	sum = 0
	for i in range(1, 10):
		sum += F(A + D * i)
	ans = 0
	while (R - L + 1) % 9 != 0:
		ans += F(A + D * R)
		R = R - 1
	ans += sum * (R - L + 1) // 9
	print(str(ans) + '\n')


x = input()
x = int(x)
for j in range(x):
	(a, d, l, r) = input().split()
	a = int(a)
	d = int(d)
	l = int(l)
	r = int(r)

	def fun(n):
		return (n - 1) % 9 + 1
	m = 0
	for i in range(9):
		m = m + fun(a + (i + 1) * d)
	s = 0
	if (r - l + 1) % 9 != 0:
		for j in range((l - 1) % 9 + 1, (l - 1) % 9 + (r - l) % 9 + 2):
			s = s + fun(a + (j - 1) * d)
	fs = m * ((r - l + 1) // 9) + s
	print(fs)


t = int(input())
for i in range(t):
	(a, d, l, r) = map(int, input().split())
	x = r - l + 1
	if x <= 9:
		ans = 0
		for j in range(l, r + 1):
			c = a + (j - 1) * d
			ans += (c - 1) % 9 + 1
		print(ans)
	else:
		s = []
		for j in range(1, 10):
			c = a + (j - 1) * d
			s.append((c - 1) % 9 + 1)
		m = r // 9
		y = r % 9
		s1 = sum(s) * m + sum(s[:y])
		l -= 1
		m = l // 9
		y = l % 9
		s2 = sum(s) * m + sum(s[:y])
		print(s1 - s2)


a = int(input())
while a > 0:
	a -= 1
	b = input()
	m = 0
	(s, d, l, r) = [int(n) for n in b.split()]
	k1 = s + d * (l - 1)
	q = r - l + 1
	k = k1
	while k > 9:
		k = sum(map(int, str(k)))
	m = 0
	st = k
	k = d
	while k > 9:
		k = sum(map(int, str(k)))
	d = k
	A = []
	for i in range(9):
		m = st
		A.append(m)
		st = (st + d) % 9
		if st == 0:
			st = 9
	k = sum(A)
	q1 = q // 9
	q = q % 9
	m = q1 * k
	m += sum(A[:q])
	print(m)


import sys

def shift(l, n):
	return l[n:] + l[:n]

def sod(n):
	if n < 10:
		return n
	sm = 0
	while n > 0:
		sm += n % 10
		n = int(n / 10)
	return sod(sm)
t = int(sys.stdin.readline())
ptrn = []
for it in range(t):
	(a, d, l, r) = map(int, sys.stdin.readline().split())
	ptrn.append(sod(a))
	fac = r - l + 1
	while True:
		ele = sod(ptrn[-1] + d)
		if ele == ptrn[0]:
			break
		ptrn.append(ele)
	ln = len(ptrn)
	l -= 1
	l = divmod(l, ln)[1]
	r = divmod(r, ln)[1]
	ptrn = shift(ptrn, l)
	x = divmod(fac, ln)
	ans = sum(ptrn[:x[1]])
	ans += sum(ptrn) * x[0]
	print(ans)
	ptrn.clear()


def F(x):
	if x < 10:
		return x
	s = 0
	while x > 0:
		s += x % 10
		x //= 10
	return F(s)
T = int(input())
while T > 0:
	T -= 1
	(a, d, L, R) = map(int, input().split())
	L -= 1
	R -= 1
	a = F(a + d * L)
	d = F(d)
	mem = {}
	ans = 0
	length = 0
	found = False
	while L <= R:
		if not found and a in mem:
			found = True
			cycleVal = ans - mem[a][0]
			cycleLength = length - mem[a][1]
			ans += (R - L + 1) // cycleLength * cycleVal
			L += (R - L + 1) // cycleLength * cycleLength
		if L > R:
			break
		mem[a] = (ans, length)
		ans += F(a)
		a = F(a + d)
		L += 1
		length += 1
	print(ans)


for _ in range(int(input())):
	(a, d, l, r) = map(int, input().split())
	x = r - l + 1
	if x <= 9:
		ans = 0
		for i in range(l, r + 1):
			term = a + (i - 1) * d
			ans += (term - 1) % 9 + 1
		print(ans)
	else:
		array = []
		for i in range(1, 10):
			term = a + (i - 1) * d
			array.append((term - 1) % 9 + 1)
		multiple = r // 9
		remains = r % 9
		s1 = sum(array) * multiple + sum(array[:remains])
		l = l - 1
		multiple = l // 9
		remains = l % 9
		s2 = sum(array) * multiple + sum(array[:remains])
		print(s1 - s2)


t = int(input())
while t > 0:
	(a, d, l, r) = map(int, input().split())
	i = a + (l - 1) * d
	j = a + (r - 1) * d
	terms = r - l + 1
	arr = list()
	if i % 9 == 0 and i > 0:
		arr.append(9)
	else:
		arr.append(i % 9)
	i += d
	k = 1
	ans = arr[0]
	while i <= j:
		if i % 9 == 0 and i > 0:
			arr.append(9)
		else:
			arr.append(i % 9)
		if arr[k] == arr[0]:
			break
		ans += arr[k]
		k += 1
		i += d
	ans = ans * (terms // k)
	for x in range(0, terms % k):
		ans += arr[x]
	print(ans)
	t -= 1


def func(n):
	strn = str(n)
	sum = 0
	for digit in strn:
		sum += int(digit)
	if sum < 10:
		return sum
	else:
		return func(sum)

def func2(n):
	return 1 + (n - 1) % 9
test = int(input())
for it in range(test):
	(a, d, l, r) = [int(x) for x in input().strip().split()]
	a = a + (l - 1) * d
	a -= 1
	r = r - l + 1
	sumo = r
	div = sumo // 9
	rem = sumo % 9
	st = a
	termsum = 0
	for i in range(9):
		termsum = termsum + st % 9
		st = (st + d) % 9
	sumo = sumo + termsum * div
	st = a
	for i in range(rem):
		sumo = sumo + st % 9
		st = (st + d) % 9
	print(sumo)


t = int(input())
for i in range(t):
	b = list(map(int, input().split()))
	a = b[0]
	d = b[1]
	l = b[2]
	r = b[3]
	c = []
	for i in range(l, r + 1):
		val = (a + (i - 1) * d) % 9
		if val == 0:
			val = val + 9
			if val in c:
				break
			else:
				c.append(val)
		elif val in c:
			break
		else:
			c.append(val)
	ln = len(c)
	rem = (r - l + 1) % ln
	div = int((r - l + 1) // ln)
	total = sum(c) * div + sum(c[:rem])
	print(total)


def m(x):
	mx = x % 9
	if mx == 0:
		mx = 9
	return mx
tc = int(input(''))
while tc > 0:
	tc -= 1
	(A, D, L, R) = map(int, input('').split())
	N = R - L + 1
	AL = m(A + (L - 1) * D)
	s = [AL]
	ss = AL
	c = m(AL + D)
	while c != s[0]:
		s.append(c)
		ss += c
		c = m(c + D)
	ans = ss * (N // len(s))
	r = N % len(s)
	for i in range(r):
		ans += s[i]
	print(ans)


def f(x):
	if x < 10:
		return x
	s = 0
	while x > 0:
		s += x % 10
		x //= 10
	return f(s)

def apsum(a, d):
	sm = 0
	x = a
	for i in range(9):
		sm += f(x)
		x += d
	return sm

def apval(a, d, n):
	return a + (n - 1) * d
dp = [[apsum(i, j) for j in range(10)] for i in range(10)]

def solve(a, d, l, r):
	sm = 0
	a = f(a)
	d = f(d)
	nl = (r - l + 1) // 9
	sm += nl * dp[a][d]
	rem = (r - l + 1) % 9
	lft = r - rem + 1
	rgt = r + 1
	for i in range(lft, rgt):
		sm += f(apval(a, d, i))
	return sm
for t in range(int(input())):
	(a, d, l, r) = [int(x) for x in input().split()]
	print(solve(a, d, l, r))


def summ(a):
	if a % 9 == 0:
		return 9
	else:
		return a % 9

def main():
	t = int(input())
	for aa in range(t):
		(a1, d, l, r) = map(int, input().split())
		i = 0
		ans = 0
		sum1 = 0
		a = [0] * 9
		a1 = summ(a1)
		d = summ(d)
		z = 0
		a[z] = summ(a1)
		for z in range(1, 9):
			a[z] = summ(a1 + summ(z * d)) + a[z - 1]
		sum1 = a[8]
		l = l - 1
		j = l % 9
		i = r % 9
		p = a[i - 1]
		q = a[j - 1]
		if i == 0:
			p = 0
		if j == 0:
			q = 0
		ans = r // 9 * sum1 + p
		xx = l // 9 * sum1 + q
		ans = ans - xx
		print(ans)
main()


def sumDigits(num):
	sum = 0
	while num:
		sum += num % 10
		num //= 10
	return sum

def F(num):
	if num < 10:
		return num
	return F(sumDigits(num))
T = int(input())
while T:
	(A, D, L, R) = input().split(' ')
	A = int(A)
	D = int(D)
	L = int(L)
	R = int(R)
	f = [0 for x in range(9)]
	f[0] = F(A + (L - 1) * D)
	d = F(D)
	sum = f[0]
	for i in range(1, 9):
		if f[i - 1] + d > 9:
			f[i] = (f[i - 1] + d) % 10 + 1
		else:
			f[i] = f[i - 1] + d
		sum += f[i]
	i = R - L + 1
	if i > 9:
		sum *= i // 9
		i %= 9
		while i:
			i -= 1
			sum += f[i]
	elif i < 9:
		sum = 0
		while i:
			i -= 1
			sum += f[i]
	print('%d' % sum)
	T -= 1


def solve():
	test = int(input())
	while test > 0:
		inp = input()
		(a, diff, l, r) = map(int, inp.split())
		i = a + (l - 1) * diff
		j = a + (r - 1) * diff
		trm = r - l + 1
		arr = list()
		if i % 9 == 0 and i > 0:
			arr.append(9)
		else:
			arr.append(i % 9)
		i += diff
		cnt = 1
		ans = arr[0]
		while i <= j:
			if i % 9 == 0 and i > 0:
				arr.append(9)
			else:
				arr.append(i % 9)
			if arr[cnt] == arr[0]:
				break
			ans += arr[cnt]
			cnt += 1
			i += diff
		ans = ans * (trm // cnt)
		for c in range(0, trm % cnt):
			ans += arr[c]
		print(ans)
		test -= 1
solve()


def digsum(n):
	if n < 10:
		return n
	n = str(n)
	return digsum(sum([int(i) for i in n]))

def sdigsum(n):
	if n < 10:
		return n
	return n - 9

def eugene(A, D, L, M):
	D = digsum(D)
	A = digsum(A + (L - 1) * D)
	cyclesum = 0
	remaindersum = 0
	ss = M - L + 1
	cycle = 9
	remainder = ss % 9
	quotient = ss // 9
	for i in range(9):
		cyclesum += A
		A = sdigsum(A + D)
	for i in range(remainder):
		remaindersum += A
		A = sdigsum(A + D)
	return quotient * cyclesum + remaindersum
for tests in range(int(input())):
	[A, D, L, M] = [int(i) for i in input().split()]
	print(eugene(A, D, L, M))


T = int(input())
for tn in range(T):
	(first, delta, l, r) = [int(x) for x in input().split()]
	res = []
	ressum = 0
	for i in range(9):
		now = (first + delta * i) % 9
		if now == 0:
			res.append(9)
		else:
			res.append(now)
		ressum = ressum + res[i]
	ans = (r - l + 1) // 9 * ressum
	count = (r - l + 1) % 9
	for i in range(count - 1, -1, -1):
		ans = ans + res[(r - i - 1) % 9]
	print(ans)


import math

def check(n):
	if n < 9:
		return n
	else:
		ans = n % 9
		if ans == 0:
			return 9
		return ans
t = int(input())
while t > 0:
	t -= 1
	sum = 0
	(a, d, l, r) = map(int, input().split())
	dig = r - l + 1
	mod = dig % 9
	div = int(dig / 9)
	nth = a + (l - 1) * d
	nth = check(nth)
	temp = 0
	for i in range(l, min(l + 8, r) + 1):
		temp += 1
		mul = 0 if temp > mod else 1
		sum += nth * (div + mul)
		nth = check(nth + d)
	print(int(sum))


def f(A, D, i):
	return (A + i * D - 1) % 9 + 1
for i in range(int(input())):
	suma = 0
	(A, D, L, R) = tuple(map(int, input().split()))
	suma += (R - L) // 9 * sum((f(A, D, i) for i in range(L, L + 9)))
	L += (R - L) // 9 * 9
	D %= 9
	for i in range(L - 1, R):
		suma += (A + i * D - 1) % 9 + 1
	print(suma)


t = int(input())

def f(x):
	s = 0
	while x > 0:
		s += x % 10
		x //= 10
	if s < 10:
		return s
	else:
		return f(s)
for i in range(0, t):
	(a, d, l, r) = map(int, input().split(' '))
	al = a + (l - 1) * d
	numc = r - l + 1
	lst = []
	c = f(al)
	c -= 1
	count = 0
	while c not in lst:
		count += c
		lst.append(c)
		c = (c + d) % 9
	curc = len(lst)
	rep = numc // curc
	rem = numc % curc
	count = count * rep + curc * rep
	for j in range(0, rem):
		count += lst[j] + 1
	print(count)


import sys
t = int(input())
while t > 0:
	(a, d, l, r) = map(int, sys.stdin.readline().split())
	x = a + (l - 1) * d
	if x % 9 == 0:
		s = 9
	else:
		s = x % 9
	dif = d % 9
	if dif == 0:
		print((r - l + 1) * s)
	elif dif == 3 or dif == 6:
		if s == 1 or s == 4 or s == 7:
			temp = (r - l + 1) // 3 * 12
		elif s == 2 or s == 5 or s == 8:
			temp = (r - l + 1) // 3 * 15
		else:
			temp = (r - l + 1) // 3 * 18
		temp2 = (r - l + 1) % 3
		if temp2 == 0:
			print(temp, '\n')
		else:
			sum1 = s
			for i in range(temp2 - 1):
				s += dif
				if s > 9:
					s -= 9
				sum1 += s
			sum1 += temp
			print(sum1, '\n')
	else:
		temp = (r - l + 1) // 9 * 45
		temp2 = (r - l + 1) % 9
		if temp2 == 0:
			print(temp, '\n')
		else:
			sum1 = s
			for i in range(temp2 - 1):
				s += dif
				if s > 9:
					s -= 9
				sum1 += s
			sum1 += temp
			print(sum1, '\n')
	t -= 1