Bom has a list of n favorite numbers which are birthday, driving license, passport number, etc After creating an email account, Bom wants to choose a password as the largest number P among all possible numbers generated by the combinations of k (1 ≤ k ≤ n) positive numbers in the favorite list so that P is divisible by 9.

Your task is writing a program to help find P the password for Bom’s email.

Input

The first line contains a positive integer T as the number of test cases in the input file. The following lines describe information of each test case including:

• One line containing two positive integers n and k,
• n following lines are n favorite numbers.

Output

The output file contains T lines; each line is the solution of the corresponding test case that is either password P or -1 in case of not finding a feasible number.

Limits

T ≤ 30
1 ≤ k ≤ n ≤ 100
1 ≤ all favorite numbers ≤ 10⁶

Example

Input:
2
3 2
1
2
3
5 2
1
2
3
4
5
Output:
-1
54