Steve có một chuỗi ~S~ chỉ chứa các chữ cái ~a~, ~b~ và ~c~, Steve được phép thực hiện thao tác sau vô số lần:

• Lấy hai chữ cái khác nhau và đứng cạnh nhau trong chuỗi ~S~ và thay thế bằng chữ cái còn lại.

Hãy giúp Steve tìm độ dài chuỗi ngắn nhất có thể sau khi áp dụng thao tác trên.

Dữ liệu

• Dòng đầu tiên chứa số test ~T~ ~(1≤T ≤100)~.
• Mỗi dòng trong số ~T~ dòng tiếp theo chứa chuỗi ~S~ (Độ dài chuỗi ~S ≤ 100~).

Kết quả

• Với mỗi test case, in ra độ dài chuỗi ngắn nhất thu được.

Ví dụ

Sample Input 1

3
cab
bcab
ccccc

Sample Output 1

2 
1
5

Giải thích

• Đối với test thứ nhất, có hai cách rút gọn ~S~: cab −→ cc hoặc cab−→ bb.
• Đối với test thứ hai, cách rút gọn tối ưu ~S~: bcab −→ aab −→ ac −→ b.
• Đối với test cuối, không thể thực hiện thao tác nào nên kết quả vẫn là dãy ~S~.

Nguồn: Free Contest 124