Eugene and function

All submissions for this problem are available.
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
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, ...}
A_{1} = 1
A_{2} = 2
A_{3} = 3
F(A_{1}) = 1
F(A_{2}) = 2
F(A_{3}) = 3
1+2+3=6
Example case 2.
A = {14, 21, 28, 35, 42, 49, 56, 63, 70, 77, ...}
A_{2} = 21
A_{3} = 28
A_{4} = 35
F(A_{2}) = 3
F(A_{3}) = 1
F(A_{4}) = 8
3+1+8=12
Author:  aangairbender 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/KFUNC 
Tags  aangairbender, cakewalk, nov15 
Date Added:  5082015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions