algospot - pi

//algospot - pi
 
#include <iostream>
#include <vector>
using namespace std;
 
#define INF 100000
 
string s;
int len;
vector<int> cache;
int dp(int idx);
 
void init()
{
    cin >> s;
    len = s.size();
    cache = vector<int>(len, -1);
}
 
int case1(int start, int end)
{
    bool flag = true;
    for (int i = start; i < end; ++i)
        if (s[i] != s[i + 1])
            flag = false;
    if (flag)
        return 1 + dp(end + 1);
    else
        return INF;
}
 
int case2(int start, int end)
{
    int count = 0;
    for (int i = start; i < end; ++i)
        if (s[i] - s[i + 1] == 1)
            ++count;
    if (count == end - start)
        return 2 + dp(end + 1);
    count = 0;
    for (int i = start; i < end; ++i)
        if (s[i] - s[i + 1] == -1)
            ++count;
    if (count == end - start)
        return 2 + dp(end + 1);
    return INF;
}
 
int case3(int start, int end)
{
    if (end - start == 2)
        if (s[end] == s[start])
            return 4 + dp(end + 1);
        else
            return INF;
 
    if (end - start == 3)
        if (s[start] == s[end - 1] && s[start + 1] == s[end])
            return 4 + dp(end + 1);
        else
            return INF;
 
    if (s[start] == s[end] && s[start] == s[start + 2] && s[start + 1] == s[end - 1])
        return 4 + dp(end + 1);
    return INF;
}
 
int case4(int start, int end)
{
    int gap = s[start + 1] - s[start];
    int count = 0;
    for (int i = start + 1; i < end; ++i)
        if (s[i + 1] - s[i] == gap)
            ++count;
    if (count == end - start - 1)
        return 5 + dp(end + 1);
    return INF;
}
 
int case5(int start, int end)
{
    return dp(end + 1) + 10;
}
 
int dp(int idx)
{
    if (idx == len)
        return 0;
    int &ret = cache[idx];
    if (ret != -1)
        return ret;
    ret = INF;
    for (int i = 2; i <= 4; ++i)
    {
        if (idx + i >= len)
            continue;
        ret = min(ret, case1(idx, idx + i));
        ret = min(ret, case2(idx, idx + i));
        ret = min(ret, case3(idx, idx + i));
        ret = min(ret, case4(idx, idx + i));
        ret = min(ret, case5(idx, idx + i));
    }
    return ret;
}
 
int main()
{
    int C;
    cin >> C;
    for (int tn = 0; tn < C; ++tn)
    {
        init();
        cout << dp(0) << "\n";
    }
}