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}\)