This is a simplified version of the problem B2. Perhaps you should read the problem B2 before you start solving B1.

Paul and Mary have a favorite string s which consists of lowercase letters of the Latin alphabet. They want to paint it using pieces of chalk of two colors: red and green. Let's call a coloring of a string wonderful if the following conditions are met:

  1. each letter of the string is either painted in exactly one color (red or green) or isn't painted; 
  2. each two letters which are painted in the same color are different; 
  3. the number of letters painted in red is equal to the number of letters painted in green; 
  4. the number of painted letters of this coloring is maximum among all colorings of the string which meet the first three conditions. 



E. g. consider a string s equal to "kzaaa". One of the wonderful colorings of the string is shown in the figure.

<image> The example of a wonderful coloring of the string "kzaaa".

Paul and Mary want to learn by themselves how to find a wonderful coloring of the string. But they are very young, so they need a hint. Help them find k — the number of red (or green, these numbers are equal) letters in a wonderful coloring.

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases. Then t test cases follow.

Each test case consists of one non-empty string s which consists of lowercase letters of the Latin alphabet. The number of characters in the string doesn't exceed 50.

Output

For each test case, output a separate line containing one non-negative integer k — the number of letters which will be painted in red in a wonderful coloring.

Example

Input


5
kzaaa
codeforces
archive
y
xxxxxx


Output


2
5
3
0
1

Note

The first test case contains the string from the statement. One of the wonderful colorings is shown in the figure. There's no wonderful coloring containing 3 or more red letters because the total number of painted symbols will exceed the string's length.

The string from the second test case can be painted as follows. Let's paint the first occurrence of each of the letters "c", "o", "e" in red and the second ones in green. Let's paint the letters "d", "f" in red and "r", "s" in green. So every letter will be painted in red or green, hence the answer better than 5 doesn't exist.

The third test case contains the string of distinct letters, so you can paint any set of characters in red, as long as the size of this set doesn't exceed half of the size of the string and is the maximum possible.

The fourth test case contains a single letter which cannot be painted in red because there will be no letter able to be painted in green.

The fifth test case contains a string of identical letters, so there's no way to paint more than one letter in red.
1
dscnjksdcnsjkvndfjkvndfjkvnkdfnv
 1
aa
 1
abbdsdndsncjksdncjkdsncknsdkcnskc
 61
kzaaa
codeforces
archive
y
xxxxxx
kzaaa
codeforces
archive
y
xxxxxx
kzaaa
codeforces
archive
y
xxxxxx
kzaaa
codeforces
archive
y
xxxxxx
kzaaa
codeforces
archive
y
xxxxxx
kzaaa
codeforces
archive
y
xxxxxx
kzaaa
codeforces
archive
y
xxxxxx
kzaaa
codeforces
archive
y
xxxxxx
kzaaa
codeforces
archive
y
xxxxxx
kzaaa
codeforces
archive
y
xxxxxx
kzaaa
codeforces
archive
y
xxxxxx
kzaaa
codeforces
archive
y
xxxxxx
y

8
 1
 7
 2
5
3
0
1
2
5
3
0
1
2
5
3
0
1
2
5
3
0
1
2
5
3
0
1
2
5
3
0
1
2
5
3
0
1
2
5
3
0
1
2
5
3
0
1
2
5
3
0
1
2
5
3
0
1
2
5
3
0
1
0

/* 
Author: Bibhash Ghosh (Zaptos)
*/

#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp" 
#define   ll                                long long int
#define   ull                               unsigned long long int
#define   cint                              const int
#define   fo(i,a,b)                         for(int i=a;i<b;++i)
#define   rfo(i,a,b)                        for(int i=a-1;i>=b;--i)
#define   foll(i,a,b)                       for(ll i = a; i < b; ++i)
#define   rfoll(i,a,b)                      for(ll i = a-1; i >= b; --i)
#define   sqr(x)                            (x)*(x)
#define   ii                                pair<int,int>
#define   vLL                               vector<ll>
#define   vi                                vector<int>
#define   vS                                vector<string>
#define   pb                                push_back
#define   ppb                               pop_back
#define   eb                                emplace_back
#define   lbd                               lower_bound
#define   ubd                               upper_bound
#define   setint                            set<int>
#define   setlong                           set<ll>
#define   setchar                           set<char>
#define   setstring                         set<string>
#define   multisetint                       multiset<int>
#define   multisetlong                      multiset<ll>
#define   multisetchar                      multiset<char>
#define   multisetstring                    multiset<string>
#define   vectorint                         vector<int>
#define   vectorlong                        vector<ll>
#define   vectorchar                        vector<char>
#define   vectorstring                      vector<string>
#define   vectorpair_int                    vector< ii >
#define   vectorpair_long                   vector< pair<ll, ll> >
#define   que_max                           priority_queue <int>
#define   que_min                           priority_queue <int, vi, greater<int> >
#define   umap                              unordered_map
#define   fastio                            ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define   decimal(k)                        fixed<<setprecision(k)
#define   PI                                3.14159265359
#define   ff                                first
#define   ss                                second
#define   all(V)                            (V).begin(),(V).end()
#define   alla(a,n)                         a, a+n
#define   sz(v)                             (ll)v.size()
#define   szz(a,n)                          sizeof(a)/(n)
#define   SORT(v)                           sort(all(v))
#define   REV                               reverse
#define   MAX                               max_element
#define   MIN                               min_element
#define   UNIQUE(v)                         sort(all(v)); v.erase(unique(v.begin(),v.end()),v.end())
#define   mem1(a)                           memset(a,-1,sizeof(a));
#define   mem0(a)                           memset(a,0,sizeof(a));
#define   mymax                             1000000000000000100
#define   mymin                             -1000000001
#define   bitcount                          __builtin_popcount
#define   gcd                               __gcd
#define   MOD                               (ll)1000000007
#define   INF                               2147483646
#define   TEST(t)                           int tc; cin>>tc; fo(t,1,tc+1)
#define   TS                                to_string
#define   len(s)                            (s).length()
#define   line                              cout << '\n';
#define   endl                              '\n'
#define   open                              {
#define   close                             }
#define   goog(tno)                         cout <<"Case #" << tno << ": "
#define   np2(S)                            ((int)pow(2.0, (int)((log((double)S) / log(2.0)) + 0.5)))

using namespace std;
using namespace std::chrono;
using namespace __gnu_pbds;

template<typename... T>
void read(T&... args) {
    ((cin >> args), ...);
}

#ifndef ONLINE_JUDGE
#define debug(x) cout << #x <<" = "; _print(x); cout << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cout << t;}
void _print(int t) {cout << t;}
void _print(string t) {cout << t;}
void _print(char t) {cout << t;}
void _print(double t) {cout << t;}
void _print(ull t) {cout << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cout << "{"; _print(p.ff); cout << ","; _print(p.ss); cout << "}";}
template <class T> void _print(vector <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(set <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(multiset <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T, class V> void _print(map <T, V> v) {cout << "[ "; for (auto i : v) {_print(i); cout << " ";} cout << "]";}


#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << endl;
        //use cout if u want to display at the bottom
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif


ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}

ll power(ll a,ll b,ll m){            //power(x,y)=x^y  %m;
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

ll power(ll a,ll b){            //power(x,y)=x^y  %m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

ll mod_inverse(ll x,ll m){
    return power(x,m-2,m);
}

ll fact(ll n){
    ll f = 1;
    for(ll i = n+1;--i;)
    {
        f = f*i;
    }
    return f;
}

ll factmod(ll n, ll m)
{
    ll f = 1;
    for(ll i = n+1;--i;)
    {
        f = ((f%m)*(i%m))%m;
    }
    return f;
}

ll ncr(ll n, ll r) {
    if(r > n - r) r = n - r;
    ll ans = 1;
    ll i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}

int isPal(string &s){
    int len=s.size();
    int flag=1;
    for(int i=0;i<len;++i){
        if(s[i]!=s[len-i-1]){
            flag=0;
            break;
        }
    }
    return flag;
}

ll isPrime(ll n)
{
    if(n < 2)
        return 0;
    for(ll i = 2; i*i <= n; i++)
        if(n%i == 0)
            return 0;
    return 1;
}

ll sumD(ll n)
{
    if(n == 0)
        return 0;
    return (n%10) + sumD(n/10);
}

vLL pfactor(ll n)
{
    vLL v;
    while (n % 2 == 0)
    {
        v.pb(2);
        n = n/2;
    }
    for (ll i = 3; i <= sqrt(n); i = i + 2)
    {
        while (n % i == 0)
        {
            v.pb(i);
            n = n/i;
        }
    }
    if (n > 2)
        v.pb(n);
    return v;
}

void arrinp(int *a, int n)
{
    fo(i,0,n)
        cin >> a[i];
}

void arrinp(ll *a, int n)
{
    fo(i,0,n)
        cin >> a[i];
}

ll asum(int *a, int st, int ed)
{
    ll sum = 0;
    fo(i,st,ed)
        sum += a[i];
    return sum;
}

ll vsum(vi &a, int st, int ed)
{
    ll sum = 0;
    fo(i,st,ed)
        sum += a[i];
    return sum;
}

int agcd(int *arr, int st, int ed)
{
    int result = arr[st];
    for (int i = st+1; i <ed; i++)
    {
        result = gcd(arr[i], result);

        if(result == 1)
        {
           return 1;
        }
    }
    return result;
}

ll alcm(int *arr, int st, int ed)
{
    ll ans = arr[st];


    for (int i = st+1; i <ed; i++)
        ans = (((arr[i] * ans)) /
                (gcd((ll)arr[i], ans)));

    return ans;
}
int vgcd(vi &arr, int st, int ed)
{
    int result = arr[st];
    for (int i = st+1; i <ed; i++)
    {
        result = gcd(arr[i], result);

        if(result == 1)
        {
           return 1;
        }
    }
    return result;
}

ll vlcm(vLL &arr, int st, int ed)
{
    ll ans = arr[st];


    for (int i = st+1; i <ed; i++)
        ans = (((arr[i] * ans)) /
                (gcd((ll)arr[i], ans)));

    return ans;
}

double median(int a[], int n)
{
    if (n % 2 != 0)
        return (double)a[n / 2];
 
    return (double)(a[(n - 1) / 2] + a[n / 2]) / 2.0;
}

vLL divisor(ll n)
{
    vLL v;
    for (int i = 1; i*i < n; i++) {
        if (n % i == 0)
            v.pb(i);
    }
    for (int i = sqrt(n); i >= 1; i--) {
        if (n % i == 0)
            v.pb(n / i);
    }
    return v;

}

vLL divpair(ll n)
{
    vLL v;
    for (int i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
            if (n/i == i)
                v.pb(i);

            else
                v.pb(i), v.pb(n/i);
        }
    }
    return v;
}

ll countDivisor(ll n)
{
     ll i,ans=0;

    for (i=1; i*i<=n; i++)
    {
        if (n % i == 0)
        {
            if (i*i == n)
                ++ans;
            else
                ans += 2;
        }
    }

    return ans;
}

int mostfreq(int *arr, int n)
{
    unordered_map<int, int> hash;
    for (int i = 0; i < n; i++)
        hash[arr[i]]++;

    int max_count = 0, res = -1;
    for (auto &i : hash) {
        if (max_count <= i.second) {
            res = i.first;
            max_count = i.second;
        }
    }

    return res;
}

ll mostfreq(vLL &arr)
{
    int n = sz(arr);
    unordered_map<ll, ll> hash;
    for (int i = 0; i < n; i++)
        hash[arr[i]]++;

    ll max_count = 0, res = -1;
    for (auto &i : hash) {
        if (max_count <= i.second) {
            res = i.first;
            max_count = i.second;
        }
    }

    return res;
}

ll kadane(int *a, int n)
{
    ll ans=0,curr=0;
    for(int i=0;i<n;i++)
    {
        curr= curr+a[i];
        curr = max(0LL,curr);
        ans=max(ans,curr);
    }
    return ans;
}

vLL arrayIntersection(int *arr1, int *arr2, int m, int n)
{
    vLL v;
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (arr1[i] < arr2[j])
            i++;
        else if (arr2[j] < arr1[i])
            j++;
        else
        {
            v.pb(arr2[j]);
            i++;
            j++;
        }
    }
    return v;
}

void leftRotate(int *arr, int d, int n)
{
    d = d % n;
    int g_c_d = gcd(d, n);
    for (int i = 0; i < g_c_d; i++) {
        int temp = arr[i];
        int j = i;

        while (1) {
            int k = j + d;
            if (k >= n)
                k = k - n;

            if (k == i)
                break;

            arr[j] = arr[k];
            j = k;
        }
        arr[j] = temp;
    }
}

vi z_algo(string &s)
{
    int n=s.size();
    vi z(n);
    for(int i=1,l=0,r=0;i<n;i++)
    {
        if(i<=r)
            z[i]=min(r-i+1, z[i-l]);
        while(i+z[i]<n && s[z[i]]==s[i+z[i]])
            z[i]++;
        if(i+z[i]-1>r)
            l=i, r=i+z[i]-1;
    }
    return z;
}

int phi(int n)
{
    int res = n;
    for(int i = 2; i*i <= n; i++)
    {
        if(n%i == 0)
        {
            res/=i;
            res *= (i-1);
            while(n%i == 0)
                n/=i;
        }
    }
    if(n>1)
        res/=n, res *= (n-1);
    return res;
}

vi dectobin(int n)
{
    int l = floor(log2(n))+1;
    vi bin(l);
    rfo(i,l,0)
        bin[i] = (!!(n & (1 << i)));
    reverse(all(bin));
    return bin;
}

int rrr(int a, int b) { return a + rand() % (b - a + 1); }
bool ispow2(ll n){ return !(n & (n-1)); }
double tick(){static clock_t oldt,newt=clock();double diff=1.0*(newt-oldt)/CLOCKS_PER_SEC;oldt=newt;return diff;}
void yes() { cout << "YES\n"; }
void no()  { cout << "NO\n"; }
void noi() { cout << "-1" << endl; }
bool notgate(ll n) { return not (n); }
string fileName(string s1,string s2) { return s1+=s2; }
ll binaryLength(ll n)
{
    return (ll)log2(n)+1;
}

int getSum(int *BITree, int index)
{
    int sum = 0;
    while (index > 0)
    {
        sum += BITree[index];
        index -= index & (-index);
    }
    return sum;
}

void updateBIT(int *BITree, int n, int index, int val)
{
    while (index <= n)
    {
    BITree[index] += val;

    index += index & (-index);
    }
}

void convert(int *arr, int n)
{
    int temp[n];
    for (int i=0; i<n; i++)
        temp[i] = arr[i];
    sort(temp, temp+n);
    for (int i=0; i<n; i++)
    {
        arr[i] = lower_bound(temp, temp+n, arr[i]) - temp + 1;
    }
}

int inversion(int *arr, int n)
{
    int invcount = 0;

    convert(arr, n);
    int BIT[n+1];
    for (int i=1; i<=n; i++)
        BIT[i] = 0;
    for (int i=n-1; i>=0; i--)
    {
        invcount += getSum(BIT, arr[i]-1);
        updateBIT(BIT, n, arr[i], 1);
    }

    return invcount;
}


/*====================================================================================================================*/
/****************************************{Code begins here}*************************************************************/
/*===================================================================================================================*/
        
bool allsame(string &s){
	fo(i,0,sz(s)){if(s[i] != s[0])
			return false;
	}
	return true;
}

bool hasTestCase = 1;
void solve_()
{
    
    string s; cin >> s;
    int l = sz(s);

    if(l == 1)
    	cout << 0;
    else if(allsame(s))
    	cout << 1;
    else
    	cout << l/2;
    line;












    
    





}



int main()
{
    fastio;
    #ifndef ONLINE_JUDGE
        string directory = "/home/bibhash/Desktop/in-out/";
        string inputfile = "input.txt";
        string outputfile = "output.txt";
        freopen(fileName(directory,inputfile).c_str(), "r", stdin);
        freopen(fileName(directory,outputfile).c_str(),"w", stdout);
    #endif
    if(hasTestCase)
    {
        TEST(tcc)
        {
            solve_();
        }
    }
    else
    {
        solve_();
    }
    return 0;


}

/*=====================================================================================*/