Loạt sút luân lưu

Xét một loạt sút luân lưu đơn giản hoá ở cuối một trận bóng đá.

Loạt sút gồm tối đa $10$ lượt. Đội thứ nhất sút lượt $1$, đội thứ hai sút lượt $2$, đội thứ nhất sút lượt $3$, và cứ luân phiên như vậy (các lượt lẻ do đội thứ nhất sút, các lượt chẵn do đội thứ hai sút). Đội ghi nhiều bàn hơn sẽ thắng; nếu hai đội ghi bằng nhau thì hoà.

Loạt sút dừng ngay lập tức khi một đội đã ghi nhiều bàn hơn số bàn tối đa mà đội kia còn có thể đạt tới với tất cả các lượt sút còn lại của mình. Ví dụ, nếu sau lượt sút thứ $7$ đội thứ nhất ghi được $1$ bàn còn đội thứ hai ghi được $3$ bàn, trọng tài thấy rằng đội thứ nhất không thể đạt tới $3$ bàn nữa nên loạt sút kết thúc tại lượt thứ $7$.

Bạn có dự đoán cho từng lượt trong $10$ lượt sút, biểu diễn bằng một xâu $s$ gồm đúng $10$ ký tự:

• nếu $s_i$ là 1 thì lượt sút thứ $i$ chắc chắn ghi bàn;
• nếu $s_i$ là 0 thì lượt sút thứ $i$ chắc chắn không ghi bàn;
• nếu $s_i$ là ? thì lượt sút thứ $i$ có thể ghi bàn hoặc không.

Hãy tính số lượt sút nhỏ nhất có thể của loạt sút, tức là thời điểm sớm nhất mà loạt sút có thể dừng, xét trên mọi cách diễn ra có thể của các lượt sút ?.

Lưu ý: trọng tài không dựa vào dự đoán của bạn khi quyết định dừng loạt sút. Bạn có thể biết một lượt nào đó chắc chắn ghi hoặc không ghi, nhưng trọng tài chỉ nhìn vào kết quả thực tế đã diễn ra.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$, số lượng bộ dữ liệu.
• Mỗi bộ dữ liệu gồm một dòng chứa xâu $s$ gồm đúng $10$ ký tự, mỗi ký tự là 1, 0 hoặc ?.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên: số lượt sút nhỏ nhất có thể của loạt sút.

Ràng buộc

• $1\le t\le 1000$
• $s$ gồm đúng $10$ ký tự thuộc {1, 0, ?}

Ví dụ