#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
// #define mid ((l + r) >> 1)
// #define int long long
#define lowbit(x) ((x) & (-x))
const int N = 1e6 + 7, M = 207, inf = 0x3f3f3f3f, mod = 1e9 + 7;
int st[N * 2], d[N * 2], num[N], p;
void Manacher(string &s)
{
    p = 0;
    string str("@");
    for (char ch : s)
        str += "#", str += ch;
    str += "#$";
    int r = 0, n = str.size(), mid = 0;
    for (int i = 1; i < n - 1; i++)
    {
        if (i <= r)
            d[i] = min(d[(mid << 1) - i], r - i + 1);
        else
            d[i] = 1;
        while (str[i + d[i]] == str[i - d[i]])
            ++d[i];
        if (i - d[i] - 1 > r)
            mid = i, r = 1 + d[i] - i;
    }
    d[n - 1] = -1;
    for (int i = n - 3; i >= 2; i -= 2)
    {
        if (d[i + d[i]] == -1 || (d[i - d[i]] == 0 && st[i + d[i] - 2] == 1))
        {
            st[i] = 1;
            num[p++] = i;
        }
        d[i] = d[i + 1] = 0;
    }
    d[n - 1] = d[n - 2] = d[0] = d[1] = 0;
    for (int i = p - 1; i >= 0; i--)
    {
        cout << num[i] / 2 << ' ';
        st[num[i]] = 0;
    }
    cout << endl;
}
void solve()
{
    string s;
    cin >> s;
    Manacher(s);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    // cout << fixed << setprecision(10) << c << endl;
}