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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '\n\nimport fractions\nimport sys\n\nf = sys.stdin\n\nif len(sys.argv) > 1:\n    f = open(sys.argv[1], "rt")\n\n\nsum_cache = {}\n\ndef sum_func(x):\n    if x < 10:\n        return x\n\n    r = sum_cache.get(x)\n    if r is not None:\n        return r\n\n    xx = 0\n    while x > 0:\n        xx += x % 10\n        x /= 10\n\n    r = sum_func(xx)\n    sum_cache[x] = r\n\n    return r\n\ndef test():\n    for n in range(1):\n        print(n, sum_func(n))\n\n    print(sum_func(int(10**18 - 1)))\n\n#~ test()\n#~ sys.exit(1)\n\ncycle_table = [\n  # Cycle len, markers              # D_kfunc\n  [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], # 1\n  [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], # 2\n  [3, [1, 0, 0, 1, 0, 0, 1, 0, 0]], # 3\n  [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], # 4\n  [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], # 5\n  [3, [1, 0, 0, 1, 0, 0, 1, 0, 0]], # 6\n  [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], # 7\n  [9, [1, 1, 1, 1, 1, 1, 1, 1, 1]], # 8\n  [1, [1, 0, 0, 0, 0, 0, 0, 0, 0]], # 9\n]\n\nNUMBER = 9\n\ndef calc(A_1, D, L, R):\n    #~ print(\'calc ===\', A_1, D, L, R)\n    A_L = A_1 + D * (L - 1)\n    A_L_kfunc = sum_func(A_L)\n    D_kfunc = sum_func(D)\n\n    #~ print(A_L, A_L_kfunc, D_kfunc)\n\n    n = R - L + 1\n\n    if D == 0:\n        return n * A_L_kfunc\n\n    cycle_len = cycle_table[D_kfunc - 1][0]\n    cycle_markers = list(cycle_table[D_kfunc - 1][1]) # copy\n    #~ print(\'cycle_len\', cycle_len)\n\n    whole_part = n // cycle_len\n    remainder = n % cycle_len\n    #~ print(\'whole_part, remainder = \', whole_part, remainder)\n\n    counts = [whole_part * x for x in cycle_markers]\n    #~ print(counts)\n\n    pos = 0\n    for i in range(remainder):\n        counts[pos] += 1\n        pos = (pos + D_kfunc) % NUMBER\n\n    #~ print(counts)\n\n    r = 0\n    for i, x in enumerate(counts):\n        value = (A_L_kfunc - 1 + i) % NUMBER + 1\n        r += value * x\n\n    return r\n\ndef calc_dumb(A_1, D, L, R):\n    #~ print(\'dumb ===\', A_1, D, L, R)\n    a = A_1 + D * (L - 1)\n\n    n = R - L + 1\n\n    r = 0\n\n    for i in range(n):\n        value = sum_func(a)\n        #~ print(a, value)\n        r += value\n        a += D\n\n    return r\n\ndef test1():\n    a1 = 1\n    L = 1\n    R = 1000\n    for d in range(100):\n        r1 = calc_dumb(a1, d, L, R)\n        r2 = calc(a1, d, L, R)\n        if r1 != r2:\n            print(a1, d, L, R, ":", r1, r2)\n\n\ndef test2():\n    a1 = 1\n    d = 9\n    L = 1\n    R = 9\n    r1 = calc_dumb(a1, d, L, R)\n    r2 = calc(a1, d, L, R)\n    print(r1, r2)\n\n#~ test1()\n#~ sys.exit(1)\n\nT = int(f.readline().strip())\n\nfor case_id in range(1, T+1):\n    A_1, D, L, R = list(map(int, f.readline().strip().split()))\n\n    r = calc(A_1, D, L, R)\n\n    print(r)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 16405