Mike là một người rất thích các bài toán dãy số. Trong thời gian rảnh rỗi Mike đã nghĩ ra một bài toán như sau:

Cho một dãy các số nguyên và nhiệm vụ của bạn là chọn ra một tập con từ tập các số nguyên này sao cho các chữ số trong tập con này không được trùng nhau và tổng của chúng là lớn nhất.

Ví dụ tập {12, 36, 45} là một tập hợp lệ trong khi tập {12, 23, 45} là không hợp lệ vì 12 và 23 có cùng chung số 2. Tương tự các tập hợp lệ như {22, 33, 44}, {13, 44, 57, 98} và các tập không hợp lệ {12, 42}, {99, 88, 78}...

Nhiệm vụ của bạn là từ tập đã cho tìm ra một tập con sao cho tổng của các phần tử trong tập con này là lớn nhất.

Input

• Dòng đầu chứa số nguyên T là số Testcase (1 <= \(T\) <= 100). Trong mỗi bộ test input có cấu trúc như sau
• Dòng đầu trong mỗi bộ test chứa số nguyên \(n\) (1 <= n <= 100)
• Dòng thứ 2 chứa \(n\) số nguyên dương (1 <= \(a[i]\) <= 100000) là tập hợp các số.

Output

• Ứng với mỗi test in tổng tối đa có thể tạo thành từ các tập con

Example

Input

1
3
12 23 35

Output

47