// Author: Arkadiusz Pawlik
// An intermediate O(n^2) solution that constructs the prefix-suffix graph
// correctly but inefficiently converts it to the DP graph.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <list>

#define CHECK(cond) do { if (!(cond)) {\
  std::cerr << "ERROR("<<__LINE__<<"): " << #cond << std::endl;\
  exit(1);\
} } while(0)

using namespace std;

struct node {
  node *prefsuf, *prefsuf2, *shorter;
  int prefsuf_len, p, len, saved;
  list<node*> children;
  node(node *shorter_, int p_, int len_)
      : prefsuf(0), prefsuf2(0),
        shorter(shorter_), prefsuf_len(0), p(p_), len(len_), saved(-1) {}
  int end() {
    return p + len;
  }
  int start() {
    return p - len;
  }
};

struct graph {
  vector<node *> L;
  vector<node *> all;
  vector<int> res;
  void check_prefsuf_len(node *n, char *w) {
    int real_len = 0;
    for (int i = 1; i < n->len; ++i) {
      if (res[n->p+i] >= n->len-i) {
        real_len = n->len-i;
        break;
      }
    }
    CHECK(n->prefsuf_len == real_len);
    if (real_len) {
      for (int i = -real_len; i < real_len; ++i) {
        CHECK(w[n->p+n->len-real_len+i] == w[n->prefsuf->p+i]);
      }
    }
  }
  void check(char *w) {
    for (int i = 0; i < all.size(); ++i) {
      check_prefsuf_len(all[i], w);
    }
  }
  void build(const char *w, int n) {
    vector<node *> G;
    L.clear();
    L.resize(n+1, 0);
    res.clear();
    res.resize(n+1, 0);
    all.push_back(new node(0, 0, 0));
    L[0] = all[0];
    node *prev = all[0];
    for(int i = 0; i < n;) {
      G.clear();
      while (0 <= i - res[i] - 1 && i + res[i] < n &&
             w[i + res[i]] == w[i - res[i] - 1]) {
        prev = new node(prev, i, ++(res[i]));
        all.push_back(prev);
        G.push_back(prev);
      }
      L[i] = prev;
      prev = all[0];
      int g = i, G_start = 0;
      res[++i] = 0;
      if (G.empty()) for (; i < res[g] + g; ++i) {
        node *n = L[g];
        CHECK(2*g-i>=0);
        CHECK(n);
        int R = g + res[g] - i, r = res[2*g-i];
        if (R > r) {
          res[i] = r;
          node *m = L[2*g-i];
          L[i] = m;
          res[i+1] = 0;
        } else {
          prev = L[2*g-i];
          CHECK(prev->len == r);
          res[i] = R;
          for (int j = 0; j < r-R; ++j)
            prev = prev->shorter;
          L[i] = prev;
          goto next;
        }
      } else for (; i < res[g] + g; ++i) {
        CHECK(G_start < G.size());
        while(true) {
          node *n = G[G_start];
          CHECK(2*g-i>=0);
          CHECK(n);
          int R = n->end() - i, r = res[2*g-i];
          if (R > r) {
            res[i] = r;
            node *m = L[2*g-i];
            L[i] = m;
            res[i+1] = 0;
            break;
          } else {
            G_start++;
            node *m = L[2*g-i];
            if (m->len != r) {
              std::clog << "X" << g <<','<<i<<','<< w << ','<<prev->len<<','<<r<< std::endl;
            }
            CHECK(m->len == r);
            n->prefsuf = m;
            n->prefsuf_len = R;
            if (G_start == G.size()) {
              res[i] = R;
              prev = m;
              for (int j = 0; j < r-R; ++j)
                prev = prev->shorter;
              L[i] = prev;
              goto next;
            }
          }
        }
      }
      next:;
    }
  }
  ~graph() {
    for (int i = 0; i < all.size(); ++i) delete all[i];
  }
  void adjust_prefsuf();
  void adjust_prefsuf2();
  void make_prefsuf_children();
  int dp();
};

// Adjusts prefsuf pointers so that they point to the right (short) palindrome.
void graph::adjust_prefsuf() {
  for (int i = 0; i < all.size(); ++i) {
    node *n = all[i];
    if (!(n->prefsuf)) continue;
    while (n->prefsuf->len != n->prefsuf_len) {
      CHECK(n->prefsuf->len = 1 + n->prefsuf->shorter->len);
      n->prefsuf = n->prefsuf->shorter;
    }
  }
}

void graph::make_prefsuf_children() {
  for (int i = 0; i < all.size(); ++i) {
    all[i]->children.clear();
  }
  for (int i = 0; i < all.size(); ++i) {
    node *n = all[i];
    if (!(n->prefsuf)) continue;
    n->prefsuf->children.push_back(n);
  }
}

bool prefsuf2_compare(const node *a, const node *b) {
  return a->len < b->len;
}

void adjust_prefsuf2_rec(node *n, vector<node *> *stack) {
  if (!stack->empty()) {
    CHECK(stack->back()->len < n->len);
  }
  node fake_node(0,0,0);
  fake_node.len = n->len/2;
  vector<node*>::iterator it = upper_bound(
      stack->begin(), stack->end(), &fake_node, prefsuf2_compare);
  if (it != stack->begin()) {
    CHECK(it == stack->end() || (*it)->len > n->len/2);
    --it;
    n->prefsuf2 = *it;
    CHECK(n->prefsuf2->len <= n->len/2);
  } else {
    n->prefsuf2 = 0;
  }
  stack->push_back(n);
  for (list<node*>::iterator it = n->children.begin(); it != n->children.end();
       ++it) {
    adjust_prefsuf2_rec(*it, stack);
  }
  stack->pop_back();
}

// Find prefsufs that fit in half-palindromes.
void graph::adjust_prefsuf2() {
  make_prefsuf_children();
  for (int i = 0; i < all.size(); ++i) {
    node *n = all[i];
    if (n->prefsuf) continue;
    vector<node *> stack;
    adjust_prefsuf2_rec(n, &stack);
  }
}

int dp_rec(node *n) {
  if (n->saved != -1) return n->saved;
  int val = n->len > 0 ? n->len - 1 : 0;
  if (n->prefsuf2)
    val = dp_rec(n->prefsuf2) + n->len - 1;
  if (n->shorter)
    val = max(val, dp_rec(n->shorter)+(n->len>1));
  return n->saved = val;
}

int graph::dp() {
  int saved = 0;
  for (int i = 0; i < all.size(); ++i)
    saved = max(saved, dp_rec(all[i]));
  return saved;
}

int alg(const char *w, int n) {
  std::vector<node*> nodes(n);
  graph G;
  G.build(w, n);
  G.adjust_prefsuf();
  G.adjust_prefsuf2();
  int result = G.dp();
  return n - result;
}


int main() {
  int Z;
  cin >> Z;
  while(Z--) {
    string s;
    cin >> s;
    cout << alg(s.c_str(), s.size()) << endl;
  }
}