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

If a sequence of numbers A1, A2, ... , AN form an arithmetic progression A, he was asked to calculate sum of F(Ai), 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: A1 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(Ai).

-----Constraints-----
- 1 ≤ T ≤ 105
- 1 ≤ A1 ≤ 109
- 0 ≤ D ≤ 109
- 1 ≤ R ≤ 1018
- 1 ≤ L ≤ R

-----Subtasks-----
- Subtask 1:  0 ≤ D ≤ 100, 1 ≤ A1 ≤ 109, 1 ≤ R ≤ 100  - 15 points
- Subtask 2:  0 ≤ D ≤ 109, 1 ≤ A1 ≤ 109, 1 ≤ R ≤ 106  - 25 points
- Subtask 3: Original constraints - 60 points

-----Example-----
Input:
2
1 1 1 3
14 7 2 4

Output:
6
12

-----Explanation-----
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: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import fractions
import sys
f = sys.stdin
if len(sys.argv) > 1:
	f = open(sys.argv[1], 'rt')
sum_cache = {}

def sum_func(x):
	if x < 10:
		return x
	r = sum_cache.get(x)
	if r is not None:
		return r
	xx = 0
	while x > 0:
		xx += x % 10
		x /= 10
	r = sum_func(xx)
	sum_cache[x] = r
	return r

def test():
	for n in range(1):
		print(n, sum_func(n))
	print(sum_func(int(10 ** 18 - 1)))
cycle_table = [[9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], [3, [1, 0, 0, 1, 0, 0, 1, 0, 0]], [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], [3, [1, 0, 0, 1, 0, 0, 1, 0, 0]], [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], [1, [1, 0, 0, 0, 0, 0, 0, 0, 0]]]
NUMBER = 9

def calc(A_1, D, L, R):
	A_L = A_1 + D * (L - 1)
	A_L_kfunc = sum_func(A_L)
	D_kfunc = sum_func(D)
	n = R - L + 1
	if D == 0:
		return n * A_L_kfunc
	cycle_len = cycle_table[D_kfunc - 1][0]
	cycle_markers = list(cycle_table[D_kfunc - 1][1])
	whole_part = n // cycle_len
	remainder = n % cycle_len
	counts = [whole_part * x for x in cycle_markers]
	pos = 0
	for i in range(remainder):
		counts[pos] += 1
		pos = (pos + D_kfunc) % NUMBER
	r = 0
	for (i, x) in enumerate(counts):
		value = (A_L_kfunc - 1 + i) % NUMBER + 1
		r += value * x
	return r

def calc_dumb(A_1, D, L, R):
	a = A_1 + D * (L - 1)
	n = R - L + 1
	r = 0
	for i in range(n):
		value = sum_func(a)
		r += value
		a += D
	return r

def test1():
	a1 = 1
	L = 1
	R = 1000
	for d in range(100):
		r1 = calc_dumb(a1, d, L, R)
		r2 = calc(a1, d, L, R)
		if r1 != r2:
			print(a1, d, L, R, ':', r1, r2)

def test2():
	a1 = 1
	d = 9
	L = 1
	R = 9
	r1 = calc_dumb(a1, d, L, R)
	r2 = calc(a1, d, L, R)
	print(r1, r2)
T = int(f.readline().strip())
for case_id in range(1, T + 1):
	(A_1, D, L, R) = list(map(int, f.readline().strip().split()))
	r = calc(A_1, D, L, R)
	print(r)


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) = input().split()
	(a, d, l, r) = (int(a), int(d), int(l), int(r))
	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))


t = int(input())
while t > 0:
	t = t - 1
	(a, d, l, r) = list(map(int, input().split()))
	s = 0
	p = a + (l - 1) * d
	for i in range(0, r - l + 1):
		if 1 <= l <= r:
			if p < 9:
				q = p
			else:
				q = (p - 1) % 9 + 1
			s = s + q
			p = p + d
	print(s)


cases = int(input())
for i in range(cases):
	(a1, d, uG, oG) = list(map(int, input().split()))
	a1 = a1 % 9 if a1 % 9 != 0 else 9
	d = d % 9 if d % 9 != 0 else 9
	sum_of = 0
	rest_of = 0
	q = (a1 + d * (uG - 1)) % 9 if (a1 + d * (uG - 1)) % 9 != 0 else 9
	q1 = q
	k = (oG - uG) % 9
	f = int((oG - uG) / 9)
	for j in range(uG, uG + 9):
		sum_of += q
		q += d
		q = q % 9 if q % 9 != 0 else 9
	for k in range(uG, uG + k + 1):
		rest_of += q1
		q1 += d
		q1 = q1 % 9 if q1 % 9 != 0 else 9
	print(sum_of * f + rest_of)


def findRemainigSum(start, digitSum, upTo):
	sum = 0
	currSum = findSumOfDigits(start)
	for i in range(0, upTo):
		sum += findSumOfDigits(currSum)
		currSum = findSumOfDigits(currSum + digitSum)
	return sum

def findSumOfDigits(num):
	if num % 9 == 0 and num != 0:
		return 9
	else:
		return num % 9
t = int(input())
while t:
	inputString = input()
	inputList = inputString.split()
	a = int(inputList[0])
	d = int(inputList[1])
	l = int(inputList[2])
	r = int(inputList[3])
	sum = 0
	diff = r - l + 1
	lDigitSum = findSumOfDigits(a + (l - 1) * d)
	dDigitSum = findSumOfDigits(d)
	if dDigitSum == 9 or dDigitSum == 0:
		sum = lDigitSum * diff
	elif dDigitSum == 3 or dDigitSum == 6:
		n1 = lDigitSum
		n2 = findSumOfDigits(lDigitSum + dDigitSum)
		n3 = findSumOfDigits(n2 + dDigitSum)
		sum = int(diff / 3) * (n1 + n2 + n3) + findRemainigSum(lDigitSum, dDigitSum, diff % 3)
	else:
		sum = int(diff / 9) * 45 + findRemainigSum(lDigitSum, dDigitSum, diff % 9)
	print(sum)
	t -= 1


t = int(input())
while t:
	par = [int(i) for i in input().split(' ')]
	(a, d, l, r) = (par[0], par[1], par[2], par[3])
	elem_array = []
	cycle_sum = 0
	for i in range(0, 9):
		elem_array.append(1 + (a + i * d - 1) % 9)
		cycle_sum = cycle_sum + elem_array[i]
	ans = 0
	if r - l > 8:
		total_cycle = (r - l + 1) / 9
		ans = ans + cycle_sum * total_cycle
		l = l + total_cycle * 9
		while l <= r:
			ans = ans + elem_array[(l - 1) % 9]
			l = l + 1
	elif r - l == 8:
		ans = cycle_sum
	else:
		while l <= r:
			ans = ans + elem_array[(l - 1) % 9]
			l = l + 1
	print(ans)
	t -= 1


def f(x):
	if x % 9 == 0:
		return 9
	else:
		return x % 9
t = int(input())
for i in range(t):
	ran = input().split()
	ran = list(map(int, ran))
	a = ran[0]
	d = ran[1]
	l = ran[2]
	r = ran[3]
	s = 0
	a = a + (l - 1) * d
	for j in range(l, r + 1):
		s += f(a)
		a += d
	print(s)


def turn(n):
	if n % 9 == 0:
		return 9
	else:
		return n % 9
t = eval(input())
while t > 0:
	(a, d, l, r) = list(map(int, input().split()))
	diff = turn(d)
	s = 0
	box = []
	box.append(0)
	for i in range(1, 10):
		box.insert(i, turn(a))
		a = a + diff
	for i in range(l, r + 1):
		index = turn(i)
		s += box[index]
	print(s)
	t = t - 1


for _ in range(eval(input())):
	(a, d, l, r) = list(map(int, input().split()))
	al = a + (l - 2) * d
	s = 0
	for i in range(l, r + 1):
		al += d
		s += al % 9 * 1 or 9
	print(s)


def f(n):
	if n < 10:
		return n
	else:
		sum = 0
		temp = n
		while temp:
			sum += temp % 10
			temp /= 10
		if sum < 10:
			return sum
		else:
			return f(sum)
t = int(input())
while t:
	(a, d, l, r) = list(map(int, input().split()))
	ap = []
	ap.append(f(a + (l - 1) * d))
	for i in range(1, 9):
		ap.append(f(ap[i - 1] + d))
	temp = int((r - l + 1) / 9)
	ans = 0
	for i in range(0, 9):
		ans += ap[i] * temp
	temp = (r - l + 1) % 9
	for i in range(0, temp):
		ans += ap[i]
	print(ans)
	t -= 1


import math

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

def ans(a, d, n):
	s = 0
	if d == 0:
		print(a * n)
	elif d == 1 or d == 2 or d == 4 or (d == 5) or (d == 7) or (d == 8):
		if n < 9:
			while n > 0:
				s = s + a
				a = f(a + d)
				n = n - 1
			print(s)
		else:
			x = 9
			while x > 0:
				s = s + a
				a = f(a + d)
				x = x - 1
			s = s * int(n / 9)
			n = n % 9
			while n > 0:
				s = s + a
				a = f(a + d)
				n = n - 1
			print(s)
	elif d == 3 or d == 6:
		if n < 3:
			while n > 0:
				s = s + a
				a = f(a + d)
				n = n - 1
			print(s)
		else:
			x = 3
			while x > 0:
				s = s + a
				a = f(a + d)
				x = x - 1
			s = s * int(n / 3)
			n = n % 3
			while n > 0:
				s = s + a
				a = f(a + d)
				n = n - 1
			print(s)
	elif a == 0:
		print(9 * (n - 1))
	else:
		print(a * n)
t = int(input())
while t > 0:
	(a, d, l, r) = list(map(int, input().split(' ')))
	n = r - l + 1
	a = a + (l - 1) * d
	a = f(a)
	d = f(d)
	ans(a, d, n)
	t -= 1