Lihwy có một dãy độ dài số ~a~ gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~.

FireGhost là bạn thân của Lihwy, cậu rất ham học và sự yêu thích đặc biệt với các số nguyên. Tuy nhiên, vì gia cảnh khó khăn, cậu không mua lấy nổi cho mình một số nguyên nào cả. Chính vì vậy, cậu quyết định sẽ mượn Lihwy các số nguyên để về nhà chơi.

Lihwy khá kĩ tính và ít khi cho ai động vào dãy số của mình. Nhưng vì tình cảm bạn bè, cậu đồng ý cho FireGhost mượn một vài con số, với điều kiện là không có chữ số nào trong những số FireGhost mượn xuất hiện nhiều hơn một lần. FireGhost muốn mượn các con số thỏa mãn điều kiện Lihwy đề ra, sao cho tổng các số mượn được có giá trị lớn nhất.

Các bạn hãy giúp cậu học trò nghèo FireGhost tính xem tổng lớn nhất của các số cậu mượn được là bao nhiêu nhé.

Input

Dòng đầu tiên chứa số nguyên ~t~ là số bộ test ~(1 \leq t \leq 3)~.

Mô tả của mỗi bộ test trong ~t~ bộ test như sau:

• Dòng đầu tiên chứa số nguyên dương ~n~ — độ dài dãy ~a~ ~(1 \leq n \leq 10^3)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1~, ~a_2~, ..., ~a_n~ ~(0 \leq a_i \leq 10^{15})~.

Output

• Gồm ~t~ dòng, dòng thứ ~i~ là tổng lớn nhất các số mà FireGhost mượn được trong bộ test thứ ~i~.

Scoring

Sample Input 1

1
5
34 23 12 45 66

Sample Output 1

68

Sample Input 2

1
5
1 31 23 13 10

Sample Output 2

33

Notes

Trong ví dụ thứ nhất, FireGhost sẽ mượn hai số nguyên giá trị ~23~ và ~45~. Cậu không thể mượn cặp số ~34~ và ~45~ vì chữ số ~4~ xuất hiện ~2~ lần. Số ~66~ không được chọn vì nó có hai chữ số giống nhau.

Trong ví dụ thứ hai, FireGhost sẽ mượn hai số nguyên giá trị ~23~ và ~10~.