Chef loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Let F(X) equals to the number of lucky digits in decimal representation of X. Chef wants to know the number of such integers X, that L ≤ X ≤ R and F(X) is a lucky number. Help him and calculate that number modulo 109+7.

-----Input-----
First line contains one integer T, the number of test cases. Each of the following T lines contains two space separated positive integers L and R.

-----Output-----
For each of the T test cases print one integer, the number of such X, that L ≤ X ≤ R and F(X) is a lucky number, modulo 1000000007.

-----Constraints-----

1 ≤ T ≤ 10

1 ≤ L ≤ R ≤ 101000

-----Example-----
Input:
4
1 100
1 10000
1 100000
4444 4447

Output:
0
16
640
2

-----Notes-----
First test case: of course, any number of less than 4 digits can't contain lucky number of lucky digits, so the answer is 0.

Second test case: 16 required numbers are 4444 4447 4474 4477 4744 4747 4774 4777 7444 7447 7474 7477 7744 7747 7774 7777.

Third test case: there are 640 required lucky numbers. Some of them are 4474, 14747, 41474, 77277, 44407, 74749.

Fourth test case: the only two required numbers are 4444 and 4447.

```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 = 'lucky = {4, 774, 7, 744, 777, 74, 747, 44, 77, 47, 474, 444, 477, 447}\nfrom functools import lru_cache\nimport sys \nsys.setrecursionlimit(10 ** 6)\nmod = 10 ** 9 + 7\nfact = [1]\nfor i in range(1, 1001):\n    fact.append(fact[-1] * i % mod)\ninv = [pow(i, mod-2, mod) for i in fact]\nC = lambda k, n: fact[n] * inv[n-k] * inv[k] % mod\ndef f(n):\n    n = [int(x) for x in n]\n    @lru_cache(None)\n    def dp(pos, cnt, free):\n        if cnt > 777:\n            return 0\n        diff = len(n) - pos \n        ans = 0\n        if free:\n            for i in lucky:\n                i -= cnt\n                if 0 <= i <= diff:\n                    ans += C(i, diff) * pow(2, i, mod) * pow(8, diff - i, mod)\n                    ans %= mod \n            return ans\n        if pos == len(n):\n            return int(cnt in lucky)\n        for i in range(10 if free else n[pos]+1):\n            ans += dp(pos+1, cnt + int(i == 4 or i == 7), free or i < n[pos])\n            ans %= mod \n        return ans \n    return dp(0, 0, 0)\n    \nt = int(input())\nfor _ in range(t):\n    l, r = input().split()\n    l = str(int(l) -1) \n    print((f(r) - f(l)) % mod)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 106346