Loại bỏ xâu con đối xứng

Cho một xâu $s$ gồm các chữ cái Latin in thường. Một xâu con liên tiếp của $s$ được gọi là đối xứng nếu đọc từ trái sang phải và từ phải sang trái đều cho cùng một kết quả.

Bạn được phép thực hiện thao tác sau bao nhiêu lần tuỳ ý: chọn một vị trí bất kỳ và thay chữ cái tại vị trí đó bằng một chữ cái Latin in thường bất kỳ.

Hãy tìm số thao tác ít nhất cần thực hiện để xâu thu được không còn chứa bất kỳ xâu con liên tiếp đối xứng nào có độ dài lớn hơn $1$.

Chẳng hạn với xâu abaa, các xâu con aba và aa đều đối xứng và có độ dài lớn hơn $1$, nên xâu này chưa thoả mãn.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $t$: số lượng bộ dữ liệu.
• Mỗi dòng trong $t$ dòng tiếp theo chứa một xâu khác rỗng gồm các chữ cái Latin in thường.

Dữ liệu ra

In ra $t$ dòng, dòng thứ $i$ là số thao tác ít nhất cần thực hiện với xâu thứ $i$.

Ràng buộc

• $1\le t\le {10}^5$
• Tổng độ dài của tất cả các xâu không vượt quá ${10}^5$.

Ví dụ