#include <iostream>
#include <vector>
using namespace std;

int main(){
    int q;
    cout << "Type the queries number: ";
    cin >> q;
    while(q--){
        string str;
        cout << "Type the text: ";
        cin >> str;
        int l = (int)str.length();
        int arr[l][l];
        for(int i=0;i<str.length();i++){
            for(int j=0;j<str.length()-i;j++){
                if(i==0){
                    arr[j][j]=1;
                    if(j!=str.length()-1)
                    arr[j+1][j]=0;
//                    cout << arr[j][j+i] << " ";
                    continue;
                }
                if(str[j+i]==str[j]){
                    arr[j][j+i]=arr[j+1][j+i-1]+2;
//                    cout << arr[j][j+i] << " ";
                    continue;
                }
                arr[j][j+i]=max(arr[j+1][j+i], arr[j][j+i-1]);
//                cout << arr[j][j+i] << " ";
            }
//            cout << endl;
        }
        cout << arr[0][l-1] << endl;
    }
}