A squarer is a simple and convenient device. You give it some positive integer X and it calculates its square.
Leha is implementing a module of this device which is responsible for squaring the numbers consisting of multiple repetitions of one digit. But it turned out that it's not as simple as he thought.
Please help him now!

-----Input-----
The first line contains one integer T denoting the number of testcases. The descriptions of T test cases follow.
Each of the following T lines contain 2 space-separated integers - N and D, respectively. It means that the number X in the corresponding testcase consists of the digit D repeated N times (in decimal representation).

-----Output-----
As the answer can be very large, we ask you to output its hash which is computed in the following way:
Let's consider the integer answer Y as a 0-indexed array starting from its leftmost digit. The hash function is calculated as:
p0*Y[0] + p1*Y[1] + ... + pM-1*Y[M-1] modulo 109 + 7 
where M is the length of the array representation of Y and p equals 23.

-----Constraints-----
- 1 ≤ T ≤ 20
- 1 ≤ D ≤ 9
- Subtask 1 (16 points): 1 ≤ N ≤ 9
- Subtask 2 (25 points): 1 ≤ N ≤ 100
- Subtask 3 (27 points): 1 ≤ N ≤ 2 × 104
- Subtask 4 (32 points): 1 ≤ N ≤ 106

-----Example-----
Input:3
1 4
3 6
3 5

Output:139
40079781
32745632

-----Explanation-----
In the first test case, X = 4 and Y = 16. Its hash equals 1*1 + 23*6 = 139.

```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 = '\nimport sys\n\nf = sys.stdin\n\nif len(sys.argv) > 1:\n f = open(sys.argv[1], "rt")\n\nT = int(f.readline().strip())\n\nMOD = 10**9 + 7\n\ndef calc(N, D):\n X = [D] * N\n\n X_d = [0] * N # X * D\n carry = 0\n for i in range(N):\n  val = D * D + carry\n  X_d[i] = val % 10\n  carry = val // 10\n assert carry < 10\n X_d.append(carry) # Could be 0, still use for convenience.\n\n product = [0] * (2*N)\n #~ print(X_d)\n #~ print(product)\n\n # (1)\n carry = 0\n cur_sum = 0\n for i in range(N):\n  cur_sum += X_d[i]\n  val = cur_sum + carry\n  product[i] = val % 10\n  carry = val // 10\n\n # (2)\n cur_sum += X_d[N]\n for i in range(N):\n  cur_sum -= X_d[i]\n  val = cur_sum + carry\n  product[N+i] = val % 10\n  carry = val // 10\n\n # (3)\n while carry > 0:\n  product.append(carry % 10)\n  carry = carry // 10\n\n while product and product[-1] == 0:\n  del product[-1]\n\n h = 0\n for x in product:\n  h = (h * 23 + x ) % MOD\n\n return h\n\nfor case_id in range(1, T+1):\n N, D = list(map(int, f.readline().strip().split()))\n\n r = calc(N, D)\n\n print(r)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13261