Nếu xâu ~S~ tồn tại một xâu con đối xứng độ dài ~L~ thì cũng sẽ tồn tại một xâu con đối xứng độ dài ~L - 2~ do ta có thể bỏ đi hai ký tự ngoài cùng của nó mà vẫn có được một xâu con đối xứng. Do đó các xâu con đối xứng ngắn nhất có thể sẽ có dạng aa hoặc aba, nên ta chỉ cần thay đổi tối đa ~1~ ký tự là đủ: thực hiện thay ~1~ ký tự bất kỳ sao cho giống ký tự kế bên.

Ta sẽ lặp qua các xâu con độ dài ~2~ và ~3~ trước để kiểm tra xem đã có xâu con đối xứng nào hay chưa, nếu có tồn tại nghĩa là ta không cần thực hiện gì nữa và số thao tác bằng ~0~. Nếu không tồn tại thì ta chỉ cần thay ~1~ ký tự như trên, tức số thao tác bằng ~1~.

Đương nhiên, các xâu có độ dài ban đầu là ~1~ sẽ không thể tạo ra bất kỳ xâu con nào có độ dài lớn hơn ~1~, nên trường hợp này ta ghi ~-1~.

#include "bits/stdc++.h"
using namespace std;

void solve() {
    string s;
    cin >> s;

    if(s.size() < 2) {
        cout << "-1\n";
        return;
    }

    int n = s.size();
    s += '#';

    for(int i = 0; i < n - 1; ++i) {
        if(s[i] == s[i + 1] || s[i] == s[i + 2]) {
            cout << "0\n";
            return;
        }
    }

    cout << "1\n";
}

int main() {
    int t;
    cin >> t;

    while(t--) solve();
}