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: interview

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)))

#~ test()
#~ sys.exit(1)

cycle_table = [
  # Cycle len, markers              # D_kfunc
  [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], # 1
  [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], # 2
  [3, [1, 0, 0, 1, 0, 0, 1, 0, 0]], # 3
  [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], # 4
  [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], # 5
  [3, [1, 0, 0, 1, 0, 0, 1, 0, 0]], # 6
  [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], # 7
  [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], # 8
  [1, [1, 0, 0, 0, 0, 0, 0, 0, 0]], # 9
]

NUMBER = 9

def calc(A_1, D, L, R):
    #~ print('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)

    #~ print(A_L, A_L_kfunc, D_kfunc)

    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]) # copy
    #~ print('cycle_len', cycle_len)

    whole_part = n // cycle_len
    remainder = n % cycle_len
    #~ print('whole_part, remainder = ', whole_part, remainder)

    counts = [whole_part * x for x in cycle_markers]
    #~ print(counts)

    pos = 0
    for i in range(remainder):
        counts[pos] += 1
        pos = (pos + D_kfunc) % NUMBER

    #~ print(counts)

    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):
    #~ print('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)
        #~ print(a, value)
        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)

#~ test1()
#~ sys.exit(1)

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
        
    else:
        if(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
    


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
    


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):
        sum=lDigitSum*diff
    else:
        if(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 

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)
    else:
        if 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