Untitled

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

#define ll long long
#define all(x) (x).begin(), (x).end()
#define f(i, n) for (int i = 0; i < n; i++)
#define trace(x) cerr << #x << ": " << x << '\n'
string s, r;
#define int long long
const int N = 1e3 + 9;
int n;
int dp[N][N];
int fun(int i, int j)
{
    if (i > j)
        return 0;
    if (i == j)
        return 1;
    if (dp[i][j] != -1)
        return dp[i][j];
    int ans = fun(i + 1, j);
    ans = max(ans, fun(i, j - 1));
    int ans2 = 1, in = -1;
    // if (s[i] == s[j])
    //     ans = max(ans, fun(i + 1, j - 1) + 2);
    for (int k = j; k > i; k--)
    {
        if (s[k] == s[i])
        {
            in = k;
            break;
        }
    }
    if (in != -1)
    {
        ans2 = fun(i + 1, in - 1) + 2;
    }
    return dp[i][j] = max(ans,ans2);
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    cin.ignore();
    while (tt--)
    {
        memset(dp, -1, sizeof dp);
        getline(cin, s);
        n = s.size();
        cout << fun(0, n - 1) << '\n';
    }
}