import os
import sys
N = []
def classify(beg, end):
    global N
    M = N[beg:end]

    if M.count(M[0]) == len(M):
        return 1

    progressive = True
    for i in range(len(M)-1):
        if M[i+1] - M[i] != M[1] - M[0]:
            progressive = False

    if progressive and abs(M[1] - M[0] == 1):
        return 2

    alternating = True
    for i in range(len(M)):
        if M[i] != M[i%2]:
            alternating = False

    if alternating:
        return 4
    if progressive:
        return 5
    return 10

INF = 987654321
cache = [None]

def memorize(beg):
    global N, INF, cache
    if beg == len(N):
        return 0

    if cache[beg] != None:
        return cache[beg]

    cache[beg] = INF
    for L in range(3, 5+1):
        if beg + L <= len(N):
            now = classify(beg, beg + L)
            rest = memorize(beg + L)
            cache[beg] = min(cache[beg], now + rest)
    return cache[beg]



T = int(input().strip())
for _ in range(T):
    N = [int(i) for i in input().strip()]
    cache = [None] * (len(N) + 2)
    answer = memorize(0)
    print(answer)