PALIN

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ụ: "aaa", "abccba", "kk" là xâu đối xứng. Còn "abc", "coco", "nero" không là xâu đối xứng.

Cho một xâu \(S\) độ dài \(N\) chỉ chứa các kí tự từ a đến z. 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. Ví dụ, đối với xâu "nerokakakcontest", nếu ta xóa đi xâu con "kakak" thì xâu sẽ trở thành "nerocontest". Ta không thể xóa đi xâu con "nero" vì đây không phải là một xâu đối xứng. Xâu con của một xâu được định nghĩa là một đoạn các kí tự liên tiếp ở xâu ban đầu.

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\) \((T \leq 5)\) số lượng bộ dữ liệu đầu vào.

\(T\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(S\) tương ứng với bộ dữ liệu thứ \(i\).

Output

Ghi ra \(T\) dòng, dòng thứ \(i\) ghi ra thời gian ít nhất để xóa toàn bộ xâu của dữ liệu thứ \(i\).

Example

3
aabcbda
abba
addbcba

3
1
2

Scoring

\(50\%\) số test tương ứng với \(50\%\) số điểm có \(|S| \leq 16\).

\(50\%\) số test còn lại \(|S| \leq 300\).