TNFSH 26

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

vector<int> v[128];
bool cmp(int a, int b){return a > b;}

int32_t main(){
    int t;
    string s;
    cin >> t;
    while(t--){
        cin >> s;
        for(int i = 'a'; i <= 'z'; ++i)v[i].clear();
        for(int i = 0; i < s.size(); ++i)v[s[i]].emplace_back(i);
        vector<int> ans;
        for(int i = 0; i < s.size(); ++i){
            for(int j = 0; j < v[s[i]].size(); ++j){
                if(ans.empty() || v[s[i]][j] < ans.back())ans.emplace_back(v[s[i]][j]);
                else *lower_bound(ans.begin(), ans.end(), v[s[i]][j], cmp) = v[s[i]][j];
            }
        }
        cout << ans.size() << '\n';
    }
    return 0;
}