Một xâu được gọi là xâu đối xứng nếu đọc xâu đó từ trái sang phải hoặc đọc từ phải sang trái đều như nhau. Ví dụ: aba, xyyx, zz là xâu đối xứng. Còn abc, xyzy, contest không là xâu đối xứng.

Cho một xâu \(s\) độ dài \(N\) chỉ chứa các kí tự latin thường. Mỗi giây, có thể xóa một xâu con của xâu \(s\), sao cho xâu con được xóa là một xâu đối xứng. Hỏi cần ít nhất bao nhiêu giây để xóa toàn bộ xâu?

Input

• Dòng đầu tiên ghi một số nguyên dương \(T\) - số bộ dữ liệu vào \((T ≤ 5)\).
• \(T\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(s\) \((|s| ≤ 300)\) tương ứng với bộ dữ liệu thứ \(i\).

Output

• Với mỗi bộ dữ liệu, in ra số giây ít nhất để xóa toàn bộ xâu.

Sample Input

3
aabcbda
abba
addbcba

Sample Output

3
1
2