Slash the string-Setter

/* Come on Code on!!!!
TEAM:     iitbhu_tesserect
College:  IIT(BHU), Varanasi
*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <ctime>
#include <cassert>
#include <climits>
#include <limits>

using namespace std;

typedef vector <int> vi;
typedef pair< int ,int > ii;

#define S(a) scanf("%d",&(a))
#define P(a) printf("%d",(a))
#define PS printf(" ")
#define NL printf("\n")
#define SL(a) scanf("%lld",&(a))
#define PL(a) printf("%lld",(a))
#define LL long long int
#define FOR(I,A,B) for(int I= (A); I<(B); ++I)
#define all(c) c.begin(), c.end()
#define stop system("pause")
#define pb push_back
#define mp make_pair
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define INDEX(arr,ind)          (lower_bound(all(arr),ind)-arr.begin())
#define ff first
#define ss second

#define imax numeric_limits<int>::max()
#define imin numeric_limits<int>::min()
#define lmax numeric_limits<ll>::max()
#define lmin numeric_limits<ll>::min()


#define N 2000 //Max string length

int z[N];
string s;
int n;
int L = 0, R = 0;


void prec(){
    n = s.size();
    L = 0;
    R = 0;
    FOR(i,0,n+1)
        z[i]=0;
}

void zAlgo(){
    for (int i = 1; i < n; i++) {
      if (i > R) {
        L = R = i;
        while (R < n && s[R-L] == s[R]) R++;
        z[i] = R-L; R--;
      } else {
        int k = i-L;
        if (z[k] < R-i+1) z[i] = z[k];
        else {
          L = i;
          while (R < n && s[R-L] == s[R]) R++;
          z[i] = R-L; R--;
        }
      }
    }
}

int main(){
    //freopen("input04.txt","r",stdin);
    //freopen("output04.txt","w",stdout);
    int t;
    S(t);
    while(t--){
        cin>>s;
        int ans = 0;
        while(s.size()){
            //cout<<s<<endl;
            //cout<<s<<endl;  //remove this statement afterwards   NOTE: Specify that the middle string should not be prefix or suffix itself
            prec();
            zAlgo();
            int mx = -1;
            FOR(i,0,n)
                mx = max(mx,z[i]);
            if(mx>0){
                //process the prefix part
                string temp = "";
                FOR(i,mx,n)
                    temp+=s[i];
                s = temp;
                ans++;
            }
            else{                //process the suffix part
                reverse(s.begin(),s.end());
                prec();
                zAlgo();
                int zx = -1;
                FOR(i,0,n)
                    zx = max(zx,z[i]);
                if(zx>0){
                    //slash the suffix
                    string temp = "";
                    FOR(i,zx,n)
                        temp+=s[i];
                    s = temp;
                    ans++;
                    reverse(s.begin(),s.end());
                }
                else{
                    //drop the last character
                    reverse(s.begin(),s.end());
                    string temp = "";
                    FOR(i,1,n)
                        temp+=s[i];
                    s = temp;
                    ans++;

                }
            }
            //cout<<s<<" "<<ans<<endl;

        }
        P(ans);
        NL;
    }
    //stop;
    return 0;
}