Alice has a set of $N$ unpleasant pairs of digits.

Consider a number bad if it satisfies the following conditions:

• Contains a pair of digits that goes in a row
• It is unpleasant

Otherwise, the number is considered good.

Your task is to determine $K$ ascending good numbers.

Input format

• The first line contains one integer $T$ that denotes the number of test cases.
• The first line of the test case contains two integers $N$ and $K$.
• The next $N$ lines contain two digits $d_1,d_2$.

Output format

Print $T$ lines. The $i^{th}$ line must contain an answer for the $i^{th}$ test case.

Note: If answer is more than $5\times10^{18}$, print -1.

Constraints

$1≤ T≤ 1000$

$0≤ n<100$

$0≤ d_1,d_2≤ 9$

$1≤ K≤ 10^{18}$