# ZeroJudge - d273: 11584 - Partitioning by Palindromes
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=d273
###### tags: `ZeroJudge` `字串` `動態規劃（Dynamic Programming）`

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

static const auto Initialize = [] {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	return nullptr;
}();

string toCut;
bool isPalidrome[1000][1000];

void Build() {
	static int i, left, right;
	memset(isPalidrome, false, sizeof(isPalidrome));
	for (i = 0; i != toCut.size() - 1; ++i) {
		left = i; right = i;
		while (0 <= left && right != toCut.size() && toCut[left] == toCut[right]) {
			isPalidrome[left][right] = true;
			--left; ++right;
		}
		left = i; right = i + 1;
		while (0 <= left && right != toCut.size() && toCut[left] == toCut[right]) {
			isPalidrome[left][right] = true;
			--left; ++right;
		}
	}
	isPalidrome[toCut.size() - 1][toCut.size() - 1] = true;
}

int main() {
	int times, DP[1001];
	cin >> times;
	while (times--) {
		cin >> toCut;
		memset(DP, 127, sizeof(DP)); DP[0] = 0;
		Build();
		for (int i = 0; i != toCut.size(); ++i)
			for (int j = 0; j <= i; ++j)
				if (isPalidrome[j][i])
					DP[i + 1] = min(DP[i + 1], DP[j] + 1);
		cout << DP[toCut.size()] << '\n';
	}
}