#include <iostream>
#include <cstring>
#include <algorithm> min과 memset을위한 헤더파일입니다.

using namespace std;


int DP[10010]; //다이나믹프로그래밍을 위한 배열이구요
char arr[10010]; //문자열을 넣을 배열입니다.

//같을때 1 단조 2 번갈아 4 등차수열 5 그외 10
int Minus(int pos) //식을 간단히 하기위해서 만든 함수입니다.
{
    return arr[pos] - arr[pos - 1];
}
int cnt3(int pos) //3가지를 한묶음으로 선택할 경우의 처리입니다.
{
    if (pos < 2) return 0; //3개부터묶어야해서 해준 예외처리입니다. 꼭필요하지는 않다고 생각되지만 혹시 몰라서 넣었습니다.
    else if (arr[pos] == arr[pos - 1] && arr[pos] == arr[pos - 2]) return 1; //세개 모두 같은경우 난이도 1
    else if (Minus(pos) == 1 && Minus(pos - 1) == 1) return 2;
    else if (Minus(pos) == -1 && Minus(pos - 1) == -1) return 2; //1씩 증가하거나 감소는 단조수열인 경우 난이도 2처리합니다.
    else if (arr[pos] == arr[pos - 2]) return 4; //323 525 같이 3가지가 번갈아 나오기 위한 식입니다.
    else if (Minus(pos) == Minus(pos - 1)) return 5; //등차수열을 밝힐 조건문입니다.
    else return 10;
//위의 Minus함수를 이용해서 나온식들입니다. 
}
int cnt4(int pos)
{
    if (pos < 3) return 0;
    else if (arr[pos] == arr[pos - 1] && arr[pos] == arr[pos - 2] && arr[pos] == arr[pos - 3]) return 1;
    else if (Minus(pos) == 1 && Minus(pos - 1) == 1 && Minus(pos - 2) == 1) return 2;
    else if (Minus(pos) == -1 && Minus(pos - 1) == -1 && Minus(pos - 2) == -1) return 2;
    else if (arr[pos] == arr[pos - 2] && arr[pos - 1] == arr[pos - 3]) return 4;
    else if (Minus(pos) == Minus(pos - 1) && Minus(pos - 1) == Minus(pos - 2)) return 5;
    else return 10;

}
int cnt5(int pos)
{
    if (pos < 4) return 0;
    else if (arr[pos] == arr[pos - 1] && arr[pos] == arr[pos - 2] && arr[pos] == arr[pos - 3] && arr[pos] == arr[pos - 4]) return 1;
    else if (Minus(pos) == 1 && Minus(pos - 1) == 1 && Minus(pos - 2) == 1 &&Minus(pos-3) == 1) return 2;
    else if (Minus(pos) == -1 && Minus(pos - 1) == -1 && Minus(pos - 2) == -1 && Minus(pos - 3) == -1) return 2;
    else if (arr[pos] == arr[pos - 2] && arr[pos - 1] == arr[pos - 3] && arr[pos] == arr[pos - 4]) return 4;
    else if (Minus(pos) == Minus(pos - 1) && Minus(pos - 1) == Minus(pos - 2) && Minus(pos - 2) == Minus(pos - 3)) return 5;
    else return 10;
}
//각각 4개의 숫자 5개의 숫자를 선택했을경우입니다.
int main()
{
#ifdef _CONSOLE
    freopen("Text.txt", "r", stdin);
#endif //파일입출력을 위한문장
    int testc;
    cin >> testc;

    while (testc--)//testc를 받아오므로 넣어주었습니다.
    {
        memset(arr, 0, sizeof(arr));
        memset(DP, -1, sizeof(DP));//새로운 케이스를 시작할때 초기화 해줍니다.

        scanf("%s", arr); //배열에 숫자가 문자열로 들어오는데 한자리씩 넣어주기위해서 scanf 를 사용하였습니다.

        DP[2] = cnt3(2);  
        DP[3] = cnt4(3);
        DP[4] = cnt5(4); //5번째 숫자까지는 각각 한가지씩 경우를 가지므로 데이터를 대입해줍니다.
        DP[5] = DP[2] + cnt3(5); //6번째의 경우 3선택 3선택이 가능하므로 두경우를 더해줍니다.
        DP[6] = min(DP[3] + cnt3(7), DP[2] + cnt4(7));
//7개의 숫자의 경우 3,4 와 4,3 선택이 가능하므로 이렇게 해줍니다.
        for (int j = 7; j < strlen(arr); j++)
        {
            DP[j] = min(DP[j - 3] + cnt3(j),min( DP[j - 4] + cnt4(j), DP[j - 5] + cnt5(j)));
        } //점화식입니다. 
        int n = strlen(arr);
        cout << DP[n-1] << endl; //값을 출력해줍니다.
    }

}