Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

You have an array of N integers and an integer K. You can perform at most K operations on the array.

In an operation :
you can chose two adjacent element from the array and concatenate them.

for example concatenating 13 and 24 results 1324.
after every operation the size of the array decreases by one.

You have to answer what is the maximum possible element of the array after performing no more than K operations.

Note: the answer might not fit into any integer data type.

Input

first line takes an integer \(T\) : number of testcases
each of the testcase takes two line of input
first line of each testcase takes two number \(N , K\) : number of elements in array, number of operations
second line of each testcase takes input of \(N\) numbers

\(1 <= T <= 100\)
\(0 <= K < N <= 1000\)
\(1 <= Ai <= 10^9\)
Sum of N over all testcase will not exceed 1000

Output

Print one integer in each testcase : the maximum possible number in the array after perfoming no more than k operation

Sample

1
7 2
10288 29 46 203 4445 1 1111

462034445

in first operation :
concatenate 203 and 4445
the array becomes 10288 29 46 2034445 1 1111

in second operation :
concatenate 46 and 2034445
the array becomes 10288 29 462034445 1 1111

the maximum element of the array is 462034445