1373_E. Sum of Digits
Let f(x) be the sum of digits of a decimal number x.

Find the smallest non-negative integer x such that f(x) + f(x + 1) + ... + f(x + k) = n.

Input

The first line contains one integer t (1 ≤ t ≤ 150) — the number of test cases.

Each test case consists of one line containing two integers n and k (1 ≤ n ≤ 150, 0 ≤ k ≤ 9). 

Output

For each test case, print one integer without leading zeroes. If there is no such x that f(x) + f(x + 1) + ... + f(x + k) = n, print -1; otherwise, print the minimum x meeting that constraint.

Example

Input


7
1 0
1 1
42 7
13 7
99 1
99 0
99 2


Output


1
0
4
-1
599998
99999999999
7997
```python
def generate_prefix(su):
    pre = ""
    if su >= 8:
        pre += '8'
        su -= 8
    if len(pre) > 0:
        nu = 9
    else:
        nu = 8
    while su > 0:
        while su >= nu:
            su -= nu
            pre += str(nu)
        nu -= 1
    pre = pre[::-1]
    return pre


def get_number(su, nines, d, k):
    last_digit_sum = 0
    with_zeros = 0
    with_nines = 0
    for i in range(k + 1):
        if d + i < 10:
            last_digit_sum += d + i
            with_nines += 1
        else:
            last_digit_sum += (d + i) % 10
            with_zeros += 1

    # assume prefix of to be prefix
    # k * prefix + with_zeros[for carry] + (nines * 9) * with_nines + 000000 * with_zeros + last_digit_sum = su
    # this is the sum of values in prefix.
    # we generate the smallest prefix with 9 not in the end.
    su -= with_zeros \
          + last_digit_sum \
          + nines * 9 * with_nines

    if su < 0 or su % (k + 1) != 0:
        return ""
    su //= k + 1
    prefix = generate_prefix(su)
    if prefix == '0':
        prefix = ''
    ret = (prefix + '9' * nines + str(d))
    return ret


for _ in range(int(input())):
    su, k = map(int, input().split())
    fans = 1e20
    for d in range(10):
        for nines in range(0, 64):
            this_ans = get_number(su, nines, d, k)
            if this_ans == "":
                continue
            else:
                if int(this_ans) < int(fans):
                    fans = this_ans
    if fans == 1e20:
        print(-1)
    else:
        print(fans)

```