Cho xâu ~S~, hãy cho biết cần thay đổi ít nhất bao nhiêu kí tự để ~S~ tồn tại xâu con có độ dài lớn hơn ~1~ là xâu đối xứng.

Input

Dòng đầu tiên chứa ~T~ (~1 \leq T \leq 10^5~), số lượng test bạn phải xử lý. ~T~ dòng tiếp theo, mỗi dòng chứa một xâu ~S~ chỉ gồm các ký tự chữ cái Latin in thường.

Tổng số ký tự của ~S~ trong tất cả các testcase không quá ~10^5~.

Output

Gồm ~T~ dòng, mỗi dòng ghi một số nguyên là đáp án của testcase đó. Nếu không thể thay đổi thỏa mãn đề bài thì ghi ~-1~.

Sample Input 1

2
dcbefab
xyzyx

Sample Output 1

1
0

Notes

Ở xâu đầu tiên, ta có thể thay ký tự thứ tư của xâu thành a để được xâu con bafab là xâu con đối xứng của xâu lớn.

Vì bản thân xâu thứ hai đã là xâu đối xứng nên ta không cần thay đổi gì cả.