Một chuỗi ký tự s chỉ gồm các chữ cái 'a' và 'b' được gọi là một chuỗi đẹp nếu số lượng các chữ cái 'a' và 'b' trong s là khác nhau.

Ví dụ: các chuỗi 'a', 'aba', 'bbbb' là chuỗi đẹp, còn các chuỗi 'ab', 'abba' thì không phải.

Cho một chuỗi ký tự s chỉ gồm các chữ cái 'a' và 'b'. Hãy tìm cách cắt chuỗi s thành một số ít nhất các chuỗi con là chuỗi đẹp.

Ví dụ, một cách cắt chuỗi s = 'aabbab' thành 2 chuỗi 'aab' và 'bab' là cách cắt hợp lệ; còn cách cắt s thành 2 chuỗi 'aabb' và 'ab' thì không hợp lệ vì hai chuỗi con không phải là chuỗi đẹp. Ngoài ra, cách cắt s thành 3 chuỗi 'a', 'a', 'bbab' là hợp lệ nhưng không phải đáp án, vì cách cắt này tạo ra 3 chuỗi con, không phải là cách cắt tối thiểu, mặc dù cả 3 chuỗi con này đều là chuỗi đẹp.

Biết rằng lời giải luôn tồn tại. Em hãy cho biết có thể cắt chuỗi s thành ít nhất bao nhiêu chuỗi con là chuỗi đẹp.

Bạn phải trả lời q truy vấn độc lập. Dữ liệu: nicestr.inp

Dòng đầu tiên của đầu vào chứa số nguyên q (1 ≤ q ≤ 100) là số truy vấn.

Tiếp theo là q dòng, dòng thứ i chứa truy vấn thứ i, gồm một chuỗi s có độ dài không quá 10⁵ và chỉ gồm các chữ cái 'a' và 'b'.

Kết quả: nicestr.out

In ra q dòng, trong đó dòng thứ i ghi câu trả lời của truy vấn thứ i, là số lượng ít nhất các chuỗi con đẹp có thể cắt ra từ chuỗi s tương ứng.