We say that a binary string (a string containing only characters '0' and '1') is pure if it does not contain either of the strings "0101" or "1010" as a subsequence.
Recall that string T is a subsequence of string S if we can delete some of the letters of S (possibly none) such that the resulting string will become T.
You are given a binary string $S$ with length $N$. We want to make this string pure by deleting some (possibly zero) characters from it. What is the minimum number of characters we have to delete?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single string $S$ with length $N$.

-----Output-----
For each test case, print a single line containing one integer — the minimum number of characters we have to delete from $S$.

-----Constraints-----
- $1 \le T \le 40$
- $1 \le N \le 1,000$
- $S$ contains only characters '0' and '1'

-----Example Input-----
4
010111101
1011100001011101
0110
111111

-----Example Output-----
2
3
0
0

-----Explanation-----
Example case 1: We can delete the first and third character of our string. There is no way to make the string pure by deleting only one character.
Example case 3: The given string is already pure, so the answer is zero.

Difficulty: VERY_HARD
Tags: Dynamic programming

Complete search
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	bi = input().strip()
	dp = [0 if i < 2 else len(bi) for i in range(6)]
	for c in bi:
		if c == '1':
			dp[3] = min(dp[3], dp[0])
			dp[0] += 1
			dp[5] = min(dp[5], dp[2])
			dp[2] += 1
			dp[4] += 1
		else:
			dp[2] = min(dp[2], dp[1])
			dp[1] += 1
			dp[4] = min(dp[4], dp[3])
			dp[3] += 1
			dp[5] += 1
	print(min(dp))


t = int(input())
while t > 0:
	st = input()
	dp = [0 if i < 2 else len(st) for i in range(6)]
	for c in st:
		if c == '1':
			dp[3] = min(dp[3], dp[1])
			dp[1] += 1
			dp[4] = min(dp[4], dp[2])
			dp[2] += 1
			dp[5] += 1
		else:
			dp[2] = min(dp[2], dp[0])
			dp[0] += 1
			dp[5] = min(dp[5], dp[3])
			dp[3] += 1
			dp[4] += 1
	print(min(dp))
	t = t - 1


import math
from math import gcd, sqrt, floor, factorial, ceil
from bisect import bisect_left, bisect_right
import bisect
import sys
from sys import stdin, stdout
import os
sys.setrecursionlimit(pow(10, 7))
import collections
from collections import defaultdict, Counter
from statistics import median
from queue import Queue
inf = float('inf')
from operator import neg
mod = pow(10, 9) + 7

def fun(l):
	m = [[l[0]]]
	for i in range(1, n):
		if m[-1][-1] == l[i]:
			m[-1] += [l[i]]
		else:
			m.append([l[i]])
	count = []
	for i in range(len(m)):
		count.append(len(m[i]))
	return count

def function(l1, index, prev, count):
	tuple = (index, prev, count)
	if tuple in dict:
		return dict[tuple]
	n = len(l1)
	if index == n:
		return 0
	if count >= 3:
		if index % 2 == prev:
			dict[tuple] = function(l1, index + 1, prev, count)
			return function(l1, index + 1, prev, count)
		else:
			dict[tuple] = l1[index] + function(l1, index + 1, prev, count)
			return dict[tuple]
	if prev == None:
		skip = l1[index] + function(l1, index + 1, prev, count)
		not_skip = function(l1, index + 1, index % 2, count + 1)
		maxa = min(skip, not_skip)
		dict[tuple] = maxa
		return maxa
	if index % 2 == prev:
		dict[tuple] = function(l1, index + 1, index % 2, count)
		return dict[tuple]
	if index % 2 != prev:
		skip = l1[index] + function(l1, index + 1, prev, count)
		not_skip = function(l1, index + 1, index % 2, 1 + count)
		maxa = min(skip, not_skip)
		dict[tuple] = maxa
		return maxa
t = int(input())
for i in range(t):
	s = input()
	l = list(s)
	n = len(l)
	l = [int(i) for i in l]
	l1 = fun(l)
	dict = defaultdict(int)
	theta = function(l1, 0, None, 0)
	print(theta)


for _ in range(int(input())):
	s = str(input())
	dp = [0, 0, len(s), len(s), len(s), len(s)]
	for i in s:
		if i == '1':
			dp[3] = min(dp[3], dp[0])
			dp[0] += 1
			dp[5] = min(dp[5], dp[2])
			dp[2] += 1
			dp[4] += 1
		else:
			dp[2] = min(dp[2], dp[1])
			dp[1] += 1
			dp[4] = min(dp[4], dp[3])
			dp[3] += 1
			dp[5] += 1
	print(min(dp))


import sys
from random import randint

def rec(x, y, b):
	if x == n:
		return 0
	if y == 3:
		return n
	if dp[x][y] != -1:
		return dp[x][y]
	if y == 1:
		p = b ^ 1
	else:
		p = b
	res = n
	if a[x] != p:
		res = min(res, rec(x, y + 1, b))
		res = min(res, 1 + rec(x + 1, y, b))
	else:
		res = min(res, rec(x + 1, y, b))
	dp[x][y] = res
	return dp[x][y]
sys.setrecursionlimit(10 ** 6)
t = int(input())
for _ in range(t):
	a = list(map(int, list(input())))
	n = len(a)
	dp = [[-1, -1, -1] for i in range(n)]
	res = rec(0, 0, 0)
	dp = [[-1, -1, -1] for i in range(n)]
	res = min(res, rec(0, 0, 1))
	print(res)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	(o, z, oz, zo, ozo, zoz) = (0, 0, 0, n, n, n)
	for i in s:
		if i == '1':
			zo = min(zo, z)
			z = z + 1
			ozo = min(ozo, oz)
			oz = oz + 1
			zoz = zoz + 1
		else:
			oz = min(oz, o)
			o = o + 1
			zoz = min(zoz, zo)
			zo = zo + 1
			ozo = ozo + 1
	print(min(o, z, oz, zo, ozo, zoz))


import numpy as np
i8 = np.int64

def solve_core(a, n):
	res = 0
	s1 = a[0]
	s2 = a[1]
	s3 = np.sum(a[2::2])
	for i in range(1, n, 2):
		t3 = s3
		for j in range(i + 1, n + 1, 2):
			res = max(res, s1 + s2 + t3)
			s2 += a[j + 1]
			t3 -= a[j]
		s1 += a[i + 1]
		s2 = a[i + 2]
		s3 -= a[i + 1]
	return res

def solve(S):
	N = len(S)
	a = np.zeros(N + 2, i8)
	i = 0
	prev = S[0]
	count = 0
	for c in S:
		if c == prev:
			count += 1
		else:
			a[i] = count
			prev = c
			count = 1
			i += 1
	else:
		a[i] = count
		i += 1
	if i < 4:
		return 0
	else:
		res = max(solve_core(a, i), solve_core(a[1:], i - 1))
		return N - res

def main():
	T = int(input())
	for _ in range(T):
		S = input()
		print(solve(S))

def __starting_point():
	main()
__starting_point()


for _ in range(int(input())):
	s = input()
	prev = None
	l = []
	S = ''
	cnt = 0
	for i in s:
		if i != prev:
			if cnt != 0:
				l.append(cnt)
			prev = i
			S += i
			cnt = 1
		else:
			cnt += 1
	l.append(cnt)
	if len(l) <= 3:
		print(0)
	else:
		ans = 0
		n = len(l)
		suf = [None] * (n + 2)
		suf[n] = suf[n + 1] = 0
		for i in range(n - 1, -1, -1):
			suf[i] = suf[i + 2] + l[i]
		curr1 = 0
		for i in range(0, n, 2):
			curr1 += l[i]
			curr2 = 0
			for j in range(i + 1, n, 2):
				curr2 += l[j]
				ans = max(ans, curr1 + curr2 + suf[j + 1])
		curr1 = 0
		for i in range(1, n, 2):
			curr1 += l[i]
			curr2 = 0
			for j in range(i + 1, n, 2):
				curr2 += l[j]
				ans = max(ans, curr1 + curr2 + suf[j + 1])
		print(len(s) - ans)


T = int(input())
for _ in range(T):
	s = input()
	l = []
	a = 0
	b = 0
	for i in s:
		if i == '1':
			if a != 0:
				l.append(a)
				a = 0
			b += 1
		else:
			if b != 0:
				l.append(b)
				b = 0
			a -= 1
	if a != 0:
		l.append(a)
	if b != 0:
		l.append(b)
	A = [0]
	B = [0]
	for i in l:
		if i < 0:
			A.append(-i + A[-1])
			B.append(B[-1])
		else:
			A.append(A[-1])
			B.append(i + B[-1])
	m = 0
	x = len(A) - 1
	for i in range(1, x + 1):
		for j in range(i, x + 1):
			m = max(m, A[j] - A[i - 1] + B[i - 1] + B[x] - B[j], B[j] - B[i - 1] + A[i - 1] + A[x] - A[j])
	print(len(s) - m)