Xóa xâu đối xứng

Xâu đối xứng là xâu mà đọc từ trái qua phải hay đọc từ phải qua trái đều như nhau. Ví dụ: $aba$ là xâu đối xứng, còn $abb$ thì không.

Cho xâu kí tự $S$ độ dài $N$ chỉ gồm các chữ cái Latin thường. Mỗi hành động được phép xóa một xâu con (gồm các kí tự liên tiếp) của xâu hiện tại, với điều kiện xâu bị xóa là xâu đối xứng. Sau khi xóa, hai phần còn lại ở hai bên được nối liền với nhau.

Ví dụ: với xâu $tinhocabatre$, nếu xóa xâu con $aba$ thì xâu trở thành $tinhoctre$. Không thể xóa xâu con $tinhoc$ vì đây không phải là xâu đối xứng.

Yêu cầu: Hãy xác định số hành động ít nhất để xóa toàn bộ xâu.

Dữ liệu vào

• Dòng đầu tiên ghi một số nguyên dương $T$ ($T\le 5$): số bộ dữ liệu.
• $T$ dòng tiếp theo, dòng thứ $i$ chứa xâu $S$ của bộ dữ liệu thứ $i$ (độ dài không quá $300$ kí tự).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số hành động ít nhất cần thiết để xóa toàn bộ xâu.

Ràng buộc

• $1\le T\le 5$.
• $1\le N\le 300$.
• $S$ chỉ gồm các chữ cái Latin thường.

Ví dụ