Xâu đối xứng là xâu nếu đọc xâu đó từ trái qua phải hoặc đọ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ỉ chứa các kí tự latin thường. Một hành động có thể xóa một xâu con của ~S~, sao cho xâu được xóa là một xâu đối xứng.

Ví dụ: Với xâu ~tinhocabatre~, nếu xóa đi 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ối thiểu để có thể xóa toàn bộ xâu.

Input

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

Output

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

Sample Input 1

2
abba
addbcba

Sample Output 1

1
2