Chuỗi Đảo

Bạn được cung cấp một chuỗi nhị phân $s$ chỉ gồm các ký tự $0$ và $1$.

Bạn có thể thực hiện hai loại thao tác trên chuỗi $s$ với số lần tùy ý và theo thứ tự bất kỳ:

• Xóa một ký tự khỏi $s$. Thao tác này tiêu tốn $1$ xu.
• Tráo đổi vị trí của hai ký tự bất kỳ trong $s$. Thao tác này hoàn toàn miễn phí, tức là tiêu tốn $0$ xu.

Giả sử chuỗi thu được sau khi thực hiện các thao tác trên là $t$. Chuỗi $t$ được coi là hợp lệ nếu với mọi $i$ từ $1$ đến $|t|$, ta có $t_i ≠q s_i$, trong đó $|t|$ là độ dài của chuỗi $t$. Chuỗi rỗng luôn luôn hợp lệ. Lưu ý rằng bạn so sánh chuỗi kết quả $t$ với chuỗi ban đầu $s$.

Hãy tìm chi phí tối thiểu để tạo ra một chuỗi $t$ hợp lệ.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 ≤ t ≤ 10^4$) là số lượng bộ dữ liệu.

Dòng duy nhất của mỗi bộ dữ liệu chứa một chuỗi nhị phân $s$ ($1 ≤ |s| ≤ 2 · 10^5$, $s_i \in {0, 1}$).

Tổng độ dài của tất cả các chuỗi $s$ trong mọi bộ dữ liệu không vượt quá $2 · 10^5$.

Kết quả

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất là chi phí tối thiểu để tạo ra chuỗi $t$ hợp lệ.

Chấm điểm

Subtask 1 (30 points). Tổng độ dài tất cả các chuỗi không vượt quá 200; Độ dài mỗi chuỗi |s| $≤ 12$

Subtask 2 (70 points). $1 ≤ t ≤ 10^4$

Ví dụ

Input

4
0
011
0101110001
111100

Output

1
1
0
4

Ghi chú

Trong bộ dữ liệu đầu tiên, bạn cần xóa một ký tự khỏi $s$ để thu được chuỗi rỗng $t$. Khi đó $t$ mới trở nên hợp lệ. Chi phí cho một lần xóa là $1$ xu.

Trong bộ dữ liệu thứ hai, bạn có thể xóa ký tự thứ hai khỏi $s$ để thu được chuỗi $01$, sau đó tráo đổi ký tự thứ nhất và thứ hai để thu được chuỗi $t = 10$. Chuỗi $t$ này hợp lệ vì $t_1 ≠q s_1$ và $t_2 ≠q s_2$. Tổng chi phí là $1$ xu.

Trong bộ dữ liệu thứ ba, bạn có thể tráo đổi $s_1$ với $s_2$, tráo đổi $s_3$ với $s_4$, tráo đổi $s_5$ với $s_7$, tráo đổi $s_6$ với $s_8$ và tráo đổi $s_9$ với $s_{10}$. Kết quả thu được chuỗi $t = 1010001110$. Mọi thao tác tráo đổi đều miễn phí, do đó tổng chi phí là $0$.