Sắp xếp chuỗi

Trong một buổi họp quản lý dự án, FullHouse Dev được giao một bài toán thú vị về xử lý chuỗi nhị phân. Đội ngũ quản lý muốn kiểm tra khả năng tư duy logic và tối ưu hóa của nhóm thông qua bài toán này. Với tinh thần đồng đội và sự sáng tạo, FullHouse Dev bắt đầu phân tích và giải quyết thách thức này.

Bài toán

FullHouse Dev được cung cấp một chuỗi nhị phân \(S\) có độ dài \(N\). Họ có thể thực hiện thao tác sau đối với chuỗi \(S\):

Chọn hai chỉ số khác nhau \(i\) và \(j\), sau đó đảo ngược các ký tự \(S_i\) và \(S_j\).

Nhiệm vụ của nhóm là tìm số lượng thao tác tối thiểu cần thực hiện để sắp xếp chuỗi \(S\). Luôn có thể sắp xếp được chuỗi với các ràng buộc đã cho.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Với mỗi test case:
  • Dòng đầu tiên chứa số nguyên \(N\) - độ dài của chuỗi \(S\).
  • Dòng thứ hai chứa chuỗi nhị phân \(S\).

OUTPUT FORMAT:

• Với mỗi test case, in ra số lượng thao tác tối thiểu cần thực hiện để sắp xếp chuỗi \(S\).

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq N \leq 10^5\)
• Tổng của \(N\) trong tất cả các test case không vượt quá \(10^6\)

Ví dụ

INPUT

2
3
101
6
110100

OUTPUT

1
2

Giải thích

• Ở test case đầu tiên, FullHouse Dev có thể chọn \(i=1\) và \(j=3\), đảo ngược \(S_1\) và \(S_3\) để được chuỗi "001", là chuỗi đã sắp xếp.
• Ở test case thứ hai, nhóm có thể thực hiện hai bước:
  1. Chọn \(i=2\) và \(j=5\), đảo ngược để được "100100".
  2. Chọn \(i=1\) và \(j=4\), đảo ngược để được "000011", là chuỗi đã sắp xếp.

Với sự nỗ lực và sáng tạo, FullHouse Dev đã giải quyết thành công bài toán, chứng minh khả năng xử lý vấn đề hiệu quả của mình.