human
In Berland, n different types of banknotes are used. Banknotes of the i-th type have denomination 10^{a_i} burles (burles are the currency used in Berland).
the denomination of banknotes of the first type is exactly 1.

Let's denote f(s) as the minimum number of banknotes required to represent exactly s burles. For example, if the denominations of banknotes used in Berland are 1, 10 and 100, then f(59) = 14: 9 banknotes with denomination of 1 burle and 5 banknotes with denomination of 10 burles can be used to represent exactly 9 ⋅ 1 + 5 ⋅ 10 = 59 burles, and there's no way to do it with fewer banknotes.

For a given integer k, find the minimum positive number of burles s that cannot be represented with k or fewer banknotes (that is, f(s) > k).

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — number of test cases.

The first line of each test case contains two integers n and k (1 ≤ n ≤ 10.
1 ≤ k ≤ 10^9).

The next line contains n integers a_1, a_2, ..., a_n (0 = a_1 < a_2 < ... < a_n ≤ 9).

Output

For each test case, print one integer — the minimum positive number of burles s that cannot be represented with k or fewer banknotes.

Example

Input

4
3 13
0 1 2
2 777
0 4
3 255
0 1 3
10 1000000000
0 1 2 3 4 5 6 7 8 9

Output

59
778
148999
999999920999999999
Using python3 can you solve the prior task?
 Can you provide a Python code to find the minimum positive number of burles s that cannot be represented with k or fewer banknotes (that is, f(s) > k)?
assistant
#Here is Python code to find the minimum positive number of burles s that cannot be represented with k or fewer banknotes (that is, f(s) > k).

import bisect
import heapq
import math
import collections
import sys
import copy
from functools import reduce
import decimal
from io import BytesIO, IOBase
import os
import itertools
import functools
from types import GeneratorType

#
# sys.setrecursionlimit(10 ** 9)
decimal.getcontext().rounding = decimal.ROUND_HALF_UP

graphDict = collections.defaultdict

queue = collections.deque

################## pypy deep recursion handling ##############
# Author = @pajenegod
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        to = f(*args, **kwargs)
        if stack:
            return to
        else:
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        return to
                    to = stack[-1].send(to)

    return wrappedfunc

################## Graphs ###################
class Graphs:
    def __init__(self):
        self.graph = graphDict(set)

    def add_edge(self, u, v):
        self.graph[u].add(v)
        self.graph[v].add(u)

    def dfs_utility(self, nodes, visited_nodes, colors, parity, level):
        global count
        if nodes == 1:
            colors[nodes] = -1
        else:
            if len(self.graph[nodes]) == 1 and parity % 2 == 0:
                if q == 1:
                    colors[nodes] = 1
                else:
                    colors[nodes] = -1
                    count += 1
            else:
                if parity % 2 == 0:
                    colors[nodes] = -1
                else:
                    colors[nodes] = 1
        visited_nodes.add(nodes)
        for neighbour in self.graph[nodes]:
            new_level = level + 1
            if neighbour not in visited_nodes:
                self.dfs_utility(neighbour, visited_nodes, colors, level - 1, new_level)

    def dfs(self, node):
        Visited = set()
        color = collections.defaultdict()
  ...