pi.py

pi.py

d = [0]*10001
full_str = ""
full_len = 0
full_hash = {}

# diff = lambda x: int(full_str[x+1]) - int(full_str[x])

def f(first,end):
	s = full_str[first:end]

	if s in full_hash: return full_hash[s]
	# print s
 	
	d = int(full_str[first+1]) - int(full_str[first])
	r_1 = True
	r_2_5 = True
	r_4 = True
 
	for j in xrange(first+1, end):
		if r_1 and full_str[first] != full_str[j]: 
			r_1 = False
		if r_2_5 and j+1 < end and int(full_str[j+1])-int(full_str[j]) != d:
			r_2_5 = False
		if r_4:
			if j%2 == 0:
				if full_str[j] != full_str[first]:
					r_4 = False
			else:
				if full_str[j] != full_str[first+1]:
					r_4 = False
 
		if not r_1 and not r_2_5 and not r_4: 
			full_hash[s] = 10
			return 10
 
	if r_1: 
		full_hash[s] = 1
		return 1
	elif r_2_5: 
		if d == 1 or d == -1: 
			full_hash[s] = 2
			return 2
		else: 
			full_hash[s] = 5
			return 5
	elif r_4: 
		full_hash[s] = 4
		return 4
	else: 
		full_hash[s] = 10
		return 10

def a():
	
	d[3] = f(0,3)
	d[4] = f(0,4)
	d[5] = f(0,5)
	d[6] = min(f(0,3), f(3,6))
	d[7] = min(d[3] + f(3,7), d[4] + f(4,7))

	for i in xrange(8, full_len+1):
		d[i] = min(
			d[i-3]+f(i-3,i), 
			d[i-4]+f(i-4,i), 
			d[i-5]+f(i-5,i))
	print d[full_len]

import sys
rl = lambda: sys.stdin.readline()
n = int(rl())

# import datetime
# aa = datetime.datetime.now()
# full_str = "12333"*2000
for i in xrange(n):
	full_str = rl().strip();
	full_len = len(full_str)
	a()
# bb = datetime.datetime.now()
# print bb-aa