/*
 * AIBOHP.cpp
 *
 *  Created on: May 29, 2014
 *      Author: Arpit Bhayani
 */

#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

#define DEBUG 0

int readline ( char * str ) {

	int i = 0;
	char ch;
	while ( (ch=getchar()) != '\n' ) {
		str[i++] = ch;
	}
	str[i] = '\0';
	return i;
}

int array[6101][6101];

int main ( int argc , char * argv[] ) {

	int t;
	char str[6110] , strr[6110];

	scanf("%d" , &t);

	getchar();

	while ( t-- ) {

		int n = readline(str);
		int k = 0;
		for ( int i = n-1 ; i >= 0 ; i-- ) {
			strr[k++] = str[i];
		}
		strr[k] = '\0';

		for ( int i = 0 ; i < n+1 ; i++ ) {
			for ( int j = 0 ; j < n+1 ; j++ ) {
				if ( i == 0 || j == 0 ) {
					array[i][j] = 0;
				}
				else if ( str[i-1] == strr[j-1] ) {
					array[i][j] = array[i-1][j-1] + 1;
				}
				else {
					array[i][j] = array[i-1][j] > array[i][j-1] ? array[i-1][j] : array[i][j-1];
				}
			}
		}

		cout << n - array[n][n] << endl;

	}
	return 0;
}