Thành muốn vẽ lên $N$ bức tường liên tiếp nhau. Mỗi bức tường có một giá trị biểu thị độ đẹp nếu được vẽ lên bức tường đó đó. Thế nhưng các bức tường lại bắt đầu bị sụp đổ dần sau những trận lũ lụt gần đây. Vì vậy Thành sẽ vừa vẽ nhanh vừa gia cố bức tường được vẽ đó để nó không bị sụp đổ.

Vào đầu mỗi ngày, Thành sẽ vẽ lên một trong $N$ bức tường. Ngày đầu tiên Thành có thể chọn bất kỳ bức tường nào. Vào các ngày tiếp theo Thành cần vẽ vào bức tường kế tiếp một bức tường đã vẽ. Vào cuối mỗi ngày, một bức tường bị đổ. Bức tường bị đổ luôn là bức tường chưa được vẽ lên và chỉ kề với duy nhất một bức tường khác.

Tổng độ đẹp cuối cùng nhận được là tổng độ đẹp các bức tường mà Thành vẽ lên. Thành mong muốn tìm cách vẽ là dù những bức tường nào bị đổ đi chăng nữa thì tổng độ đẹp cuối cùng tối thiểu là $B$.

Yêu cầu: Hãy giúp Thành tìm được giá trị $B$ lớn nhất có thể.

Input

Dòng đầu tiên ghi duy nhất một số nguyên $T≤5$ là số lượng trường hợp test. Mỗi nhóm dòng trong số $T$ nhóm dòng sau có cấu trúc như sau:

• Dòng thứ nhất gồm một số nguyên: $N$.
• Dòng thứ hai chứa một xâu gồm $N$ chữ số trong khoảng từ 0 đến 9, chữ số thứ $i$ biểu thị độ đẹp của bức tường thứ $i$ nếu được vẽ lên.

Output

• Ghi ra $T$ dòng, mỗi dòng ghi một số nguyên là giá trị $B$ lớn nhất tìm được.

Scoring

• Subtask #1 ($50\%$ số điểm): $2≤N≤100$.
• Subtask #2 ($50\%$ số điểm): $2≤N≤10^6$.

1
3
535

8