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:

• 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á 105 và chỉ gồm các chữ cái 'a' và 'b'.

Kết quả:

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.

Ràng buộc:

• Có 70% số test ứng với 70% số điểm của bài với s có độ dài không quá ~10^2~
• Có 30% số test ứng với 30% số điểm của bài với s có độ dài không quá ~10^5~

Ví dụ:

input

2
aabbab
abb

output

2
1