Mex của một xâu chữ số là giá trị của chữ số bé nhất chưa xuất hiện lần nào trong xâu đó. Trong trường hợp tất cả các chữ số đều xuất hiện ít nhất một lần trong xâu thì Mex của xâu sẽ có giá trị là ~10~.

Ví dụ Mex của "12" là ~0~, Mex của "102210" là ~3~, Mex của "0123456789" là ~10~

Cho một xâu gồm ~N~ phần tử, tìm cách chia xâu đã cho thành một hoặc một số xâu con liên tiếp sao cho tổng Mex của tất cả xâu con liên tiếp là lớn nhất.

Xâu b là xâu con liên tiếp của a nếu ta có thể tạo ra b bằng cách bỏ một vài (hoặc không, hoặc toàn bộ) ký tự ở đầu và bỏ một vài (hoặc không, hoặc toàn bộ) ký tự ở đuôi của xâu a.

Input

• Dòng đầu tiên là một số nguyên dương ~T (T \leq 10^5)~ là số lượng bộ test.
• Dòng đầu tiên của mỗi bộ test là số nguyên dương ~N~.
• Dòng tiếp theo là xâu gồm ~N~ chữ số từ ~0~ tới ~9~.

Output

• Gồm ~T~ dòng, mỗi dòng in ra một số duy nhất là tổng Mex lớn nhất của các xâu con liên tiếp sau khi chia.

Sample input

8
2
01
4
1111
5
01100
3
101
4
0000
5
01010
20
92304767012374063582
10
0123456789

Sample output

2
0
5
2
4
5
11
10

Tính điểm

Trong tất cả các test ~N \leq 10^5~, tổng ~N~ của các bộ test không vượt quá ~10^6~

• Subtask 1: 30% số test có ~N \leq 10^3~, tổng ~N~ của các bộ test không vượt quá ~10^4~
• Subtask 2: 30% số test các xâu chỉ gồm chữ số ~0~ và ~1~
• Subtask 3: 40% số test không có điều kiện gì thêm