Lớp 12 chuyên hóa có nhiều học sinh lười học, trong một lần ban quản lí tự học đi trực bắt gặp Mạnh đang chơi trò chơi đếm số bằng điện thoại. Thầy giáo trực yêu cầu Mạnh viết bản kiểm điểm đồng thời giao cho Mạnh ~N~ chữ số (có ít nhất 2 chữ số khác 0) và yêu cầu sử dụng hết ~N~ chữ số đó ghép thành 2 số tự nhiên sau đó đặt dấu cộng ở giữa sao cho được tổng nhỏ nhất. Tất nhiên, 2 số tạo thành đều không được có chữ số 0 ở đầu.

Mạnh đang cầm một chiếc điện thoại nhắn tin ra ngoài và rất muốn nhờ các bạn đội tuyển tin giải giúp bài toán trên.

Yêu cầu: Hãy tìm tổng nhỏ nhất có thể tạo được từ ~N~ chữ số đã cho.

Input

• Dòng đầu chứa số nguyên ~T~ (~T \le 100~) là số dòng trong file dữ liệu.
• Mỗi dòng trong ~T~ dòng tiếp theo ghi số nguyên dương ~N~ (~N \le 20~) và ~N~ chữ số tương ứng sau đó. Mỗi số cách nhau một dấu cách.

Output

• Ghi ra tổng nhỏ nhất mà Mạnh có thể trả lời thầy giáo.

Sample Input 1

2
5 1 2 7 8 9
6 3 4 2 2 2 2

Sample Output 1

207
447