Banknotes solution codeforces

Banknotes solution codeforces

In Berland, nn different types of banknotes are used. Banknotes of the ii-th type have denomination 10ai10ai burles (burles are the currency used in Berland); the denomination of banknotes of the first type is exactly 11.

Let’s denote f(s)f(s) as the minimum number of banknotes required to represent exactly ss burles. For example, if the denominations of banknotes used in Berland are 111010 and 100100, then f(59)=14f(59)=1499 banknotes with denomination of 11 burle and 55 banknotes with denomination of 1010 burles can be used to represent exactly 91+510=599⋅1+5⋅10=59 burles, and there’s no way to do it with fewer banknotes.

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

Input

Banknotes solution codeforces

The first line contains a single integer tt (1t1041≤t≤104) — number of test cases.

The first line of each test case contains two integers nn and kk (1n10;1k1091≤n≤10;1≤k≤109).

The next line contains nn integers a1,a2,,ana1,a2,…,an (0=a1<a2<<an90=a1<a2<⋯<an≤9).

Output

Banknotes solution codeforces

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

Example
input

Copy

Banknotes solution codeforces

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

Banknotes solution codeforces

Copy
59
778
148999
999999920999999999

Leave a Comment