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 \le k \le 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

Limits

• ~T \le 30~
• ~1 \le k \le n \le 100~
• ~1 \le~ all favorite numbers ~\le~ ~10^6~

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.

Sample Input

2
3 2
1
2
3
5 2
1
2
3
4
5

Sample Output

-1
54