Polycarp has a poor memory. Each day he can remember no more than $3$ of different letters.

Polycarp wants to write a non-empty string of $s$ consisting of lowercase Latin letters, taking minimum number of days. In how many days will he be able to do it?

Polycarp initially has an empty string and can only add characters to the end of that string.

For example, if Polycarp wants to write the string lollipops, he will do it in $2$ days:

on the first day Polycarp will memorize the letters l, o, i and write lolli;

On the second day Polycarp will remember the letters p, o, s, add pops to the resulting line and get the line lollipops.

If Polycarp wants to write the string stringology, he will do it in $4$ days:

in the first day will be written part str;

on day two will be written part ing;

on the third day, part of olog will be written;

on the fourth day, part of y will be written.

For a given string $s$, print the minimum number of days it will take Polycarp to write it.


-----Input-----

The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of a non-empty string $s$ consisting of lowercase Latin letters (the length of the string $s$ does not exceed $2 \cdot 10^5$) — the string Polycarp wants to construct.

It is guaranteed that the sum of string lengths $s$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print a single number — minimum number of days it will take Polycarp to write the string $s$ from memory.


-----Examples-----

Input
6
lollipops
stringology
abracadabra
codeforces
test
f
Output
2
4
3
4
1
1


-----Note-----

None

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
linesPerTest = 1
testArguments = []
i = 0
totalLines = 1
while i <= totalLines:
	line = sys.stdin.readline().rstrip('\n')
	if i == 0:
		totalLines = linesPerTest * int(line)
	else:
		testArguments.append(line)
	i += 1
testCases = []
for j in range(0, len(testArguments), linesPerTest):
	testCases.append(testArguments[j:j + linesPerTest])

def f(testArguments):
	word = testArguments[0]
	days = 0
	memory = set()
	counter = 0
	for letter in word:
		if letter not in memory:
			if counter < 3:
				memory.add(letter)
				counter += 1
			elif counter == 3:
				if letter not in memory:
					memory = set()
					memory.add(letter)
					counter = 0
					counter += 1
					days += 1
	if counter != 0:
		days += 1
	return days
for testCase in testCases:
	print(f(testCase))


import sys

def solve():
	inp = sys.stdin.readline
	s = inp().strip()
	a = set()
	r = 0
	for i in s:
		a.add(i)
		if len(a) > 3:
			a = {i}
			r += 1
	if len(a) > 0:
		r += 1
	print(r)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from math import ceil

def solver(s):
	memorized = set()
	ans = 0
	for letter in s:
		memorized.add(letter)
		if len(memorized) > 3:
			ans += 1
			memorized = set()
			memorized.add(letter)
	if len(memorized):
		return ans + 1
	return ans

def main():
	t = int(input())
	for _ in range(t):
		s = input()
		print(solver(s))
main()


import sys
import math
from itertools import accumulate

def read_string():
	return sys.stdin.readline().strip()

def read_int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def solve():
	s = read_string()
	cur = set()
	res = 0
	for i in range(len(s)):
		if len(cur) == 3 and s[i] not in cur:
			res += 1
			cur = set()
			cur.add(s[i])
		else:
			cur.add(s[i])
	print(res + 1)
T = int(input())
for _ in range(T):
	solve()


def kil_(a):
	K = 0
	fuga = set()
	for i in range(len(a)):
		if not a[i] in fuga:
			if len(fuga) < 3:
				fuga.add(a[i])
			else:
				K += 1
				fuga = set()
				fuga.add(a[i])
	if len(fuga) > 0:
		K += 1
	return K

def kil(a):
	t = int(input())
	A = ''
	for i in range(t):
		A += str(kil_(a())) + '\n'
	print(A[:-1])

def ik():
	return list(input())
kil(ik)


def solve():
	name = input()
	(c1, c2, c3) = (None, None, None)
	cnt = 0
	for c in name:
		if c1 is None or c == c1:
			c1 = c
			continue
		elif c2 is None or c == c2:
			c2 = c
			continue
		elif c3 is None or c == c3:
			c3 = c
			continue
		else:
			cnt += 1
			c1 = c
			(c2, c3) = (None, None)
	if c1 is not None:
		cnt += 1
	print(cnt)
tc = int(input())
for _ in range(tc):
	solve()


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
num_of_tests = inp()
for n in range(num_of_tests):
	count = 0
	word = insr()
	memory = set()
	for c in word:
		if c not in memory:
			if len(memory) == 3:
				count += 1
				memory = {c}
			else:
				memory.add(c)
	if len(memory) > 0:
		count += 1
	print(count)


n = int(input())
for t in range(n):
	s = input()
	st = set()
	cnt = 1
	for i in s:
		if len(st) == 3:
			if i in st:
				continue
			else:
				st.clear()
				cnt += 1
				st.add(i)
		else:
			st.add(i)
	print(cnt)


def ss(s):
	count = 1
	store = []
	for i in s:
		if i not in store:
			store.append(i)
		if len(store) == 4:
			count += 1
			store = [i]
	return count
for _ in range(int(input())):
	s = input()
	print(ss(s))


testcases = int(input())
while testcases > 0:
	testcases -= 1
	s = input()
	total_days = 0
	diff_letters = set()
	for i in s:
		diff_letters.add(i)
		if len(diff_letters) > 3:
			total_days += 1
			diff_letters.clear()
			diff_letters.add(i)
	if len(diff_letters) > 0:
		total_days += 1
	print(total_days)


import math
test = int(input())
ans = []
g = set()
for i in range(test):
	ans.append(1)
	x = input()
	g.clear()
	for j in x:
		g.add(j)
		if len(g) > 3:
			g.clear()
			g.add(j)
			ans[i] = ans[i] + 1
for i in ans:
	print(i, sep=' ')


numberofcases = int(input())
listofcases = []
for tc in range(numberofcases):
	testcase = input()
	listofcases.append(testcase)
for item in listofcases:
	count = 0
	dictionary = {}
	for character in item:
		dictionary[character] = ''
		if len(dictionary) == 4:
			count += 1
			dictionary = {}
			dictionary[character] = ''
	if len(dictionary) > 0:
		count += 1
	print(count)


k1 = int(input())
l = []
for i in range(k1):
	l.append(input())
for str in l:
	s = set()
	c = 0
	for i in str:
		s.add(i)
		if len(s) > 3:
			c = c + 1
			s = set(i)
	if len(s) > 0:
		c = c + 1
	print(c)


import sys
import heapq
input = sys.stdin.readline
from collections import Counter, defaultdict

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def main():
	string = input().strip()
	pointer = 0
	seen = set()
	count = 0
	for pointer in range(len(string)):
		char = string[pointer]
		seen.add(char)
		if len(seen) > 3:
			seen.clear()
			count += 1
			seen.add(char)
	print(count + 1)
t = inp()
for _ in range(t):
	main()


def days(string):
	set_ = set()
	n = 1
	for i in string:
		set_.add(i)
		if len(set_) > 3:
			n += 1
			set_ = set(i)
	return n
t = int(input())
for _ in range(t):
	string = input()
	print(days(string))


n = int(input())
test_cases = []
for i in range(n):
	test_cases.append(input())

def string_from_memory(s):
	res = 1
	cur = set()
	for i in s:
		if not i in cur:
			if len(cur) == 3:
				res += 1
				cur = set()
			cur.add(i)
	from math import ceil
	return res
for i in test_cases:
	print(string_from_memory(i))


def countDays(word):
	days = 0
	letters = []
	for c in word:
		if c not in letters:
			if len(letters) == 3:
				days += 1
				letters = [c]
			else:
				letters.append(c)
	return days + 1
assert countDays('lollipops') == 2
assert countDays('stringology') == 4
assert countDays('abracadabra') == 3
assert countDays('codeforces') == 4
assert countDays('test') == 1
assert countDays('f') == 1
for _ in range(int(input())):
	print(countDays(input()))


def solve():
	(word, memory, days) = (input(), set(), 0)
	for char in word:
		memory.add(char)
		if len(memory) > 3:
			memory = set()
			days += 1
		memory.add(char)
	print(days + (1 if len(memory) else 0))

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


def count_days(s):
	day_lst = []
	days_cnt = 0
	for char in s:
		if len(day_lst) < 3:
			if char not in day_lst:
				day_lst.append(char)
		elif len(day_lst) == 3:
			if char not in day_lst:
				day_lst.clear()
				day_lst.append(char)
				days_cnt += 1
	if day_lst:
		days_cnt += 1
	return days_cnt
t = int(input())
while t:
	inp = input()
	print(count_days(inp))
	t -= 1


for _ in range(int(input())):
	s = set()
	days = 1
	for x in input():
		s.add(x)
		if len(s) == 4:
			days += 1
			s = {x}
	print(days)


t = int(input())
strings = []
for _ in range(t):
	s = input()
	strings.append(s)
for s in strings:
	ans = 0
	letters = set()
	for letter in s:
		if letter not in letters:
			if len(letters) + 1 == 4:
				letters.clear()
				ans += 1
			letters.add(letter)
	print(ans + 1)


def answer_func(word):
	memory = set()
	todays_letters = 0
	days = 0
	for letter in word:
		if not letter in memory and len(memory) >= 3:
			memory.clear()
			days += 1
			todays_letters = 0
		memory.add(letter)
		todays_letters += 1
	if todays_letters > 0:
		days += 1
	return days
tests = int(input())
for test in range(tests):
	word = input()
	print(answer_func(word))


import sys
input = sys.stdin.readline

def solve():
	a = input().strip()
	b = set()
	ans = 1
	for i in range(len(a)):
		if a[i] not in b:
			if len(b) == 3:
				ans += 1
				b = set()
			b.add(a[i])
	print(ans)
tc = int(input())
for i in range(tc):
	solve()


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	s = input()
	days = 0
	ok = set()
	for i in s:
		ok.add(i)
		if len(ok) > 3:
			days += 1
			ok = {i}
	print(days + 1)
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	s = input()
	days = 1
	seen = set()
	for char in s:
		seen.add(char)
		if len(seen) > 3:
			seen.clear()
			days += 1
			seen.add(char)
	print(days)


def sol():
	s = input()
	let = set()
	count = 0
	for i in s:
		let.add(i)
		if len(let) > 3:
			count += 1
			let.clear()
			let.add(i)
	if len(let) != 0:
		count += 1
	print(count)
for _ in range(int(input())):
	sol()


for i in range(int(input())):
	s = input()
	c = 0
	a = []
	for i in s:
		if i not in a:
			a.append(i)
		if len(a) == 4:
			c += 1
			a = [i]
	print(c + bool(len(a)))


for h in range(int(input())):
	s = input()
	c = 1
	d = []
	for i in s:
		if i not in d and len(d) == 3:
			c += 1
			d = []
			d.append(i)
		elif i not in d:
			d.append(i)
	print(c)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	word = input().rstrip()
	memo = set()
	day = 1
	for i in word:
		memo.add(i)
		if len(memo) > 3:
			day += 1
			memo.clear()
			memo.add(i)
	print(day)


tests = int(input())
for _ in range(tests):
	word = input()
	n = len(word)
	cur = set()
	total = 0
	for char in word:
		if char not in cur:
			if len(cur) < 3:
				cur.add(char)
			else:
				total += 1
				cur = set([char])
	if cur:
		total += 1
	print(total)


def solve(s):
	ans = 0
	t = set()
	for i in s:
		t.add(i)
		if len(t) > 3:
			ans += 1
			t = set()
			t.add(i)
	if t:
		ans += 1
	return ans
t = int(input())
for _ in range(t):
	s = input()
	print(solve(s))


count = int(input())
days = 1
for i in range(count):
	next = input()
	used_letters = []
	for j in next:
		if len(used_letters) < 3:
			if j not in used_letters:
				used_letters.append(j)
		elif len(used_letters) == 3:
			if j not in used_letters:
				used_letters.clear()
				used_letters.append(j)
				days += 1
	print(days)
	days = 1


t = int(input())
for i in range(t):
	x = input()
	if len(x) < 4:
		print(1)
	else:
		day = 0
		mem = set()
		for k in x:
			if len(mem) == 3 and k not in mem:
				day += 1
				mem = set()
				mem.add(k)
			else:
				mem.add(k)
		print(day + 1)


import sys

def run():
	word = input()
	day_count = 1
	lets = set()
	for c in word:
		if c in lets or len(lets) < 3:
			lets.add(c)
		else:
			day_count += 1
			lets = {c}
	print(day_count)
t = int(input())
for _ in range(t):
	run()


t = int(input())
result = []
for n in range(t):
	string = input()
	d = 0
	i = 0
	l = []
	for i in string:
		if i not in l:
			if len(l) == 3:
				d += 1
				l.clear()
			l.append(i)
	result.append(d + 1)
for i in range(t):
	print(result[i])


result = []
for t in range(int(input())):
	s = list(input())
	se = set()
	r = 1
	for i in s:
		if i not in se:
			if len(se) < 3:
				se.add(i)
			else:
				r += 1
				se.clear()
				se.add(i)
	result.append(r)
for i in result:
	print(i)


def test():
	s = input().strip()
	memory = []
	days = 0
	for c in s:
		if c not in memory and len(memory) == 3:
			memory = []
			days += 1
		if c not in memory:
			memory.append(c)
	if len(memory) > 0:
		days += 1
	print(days)
t = int(input())
for i in range(1, t + 1):
	test()


t = int(input())
for i in range(t):
	s = input()
	p = 0
	k = []
	for c in s:
		if len(k) == 3 and (not c in k):
			k = []
		if not c in k:
			k.append(c)
			p += 1
	if p % 3 == 0:
		print(int(p / 3))
	else:
		print(int(p / 3) + 1)


for t in range(int(input())):
	string = input()
	count = 0
	s = set()
	for i in string:
		s.add(i)
		if len(s) > 3:
			count += 1
			s.clear()
			s.add(i)
	if len(s) != 0:
		count += 1
	print(count)


t = int(input())
for _ in range(t):
	s = input()
	m = set()
	step = 1
	flag = False
	for el in s:
		if not el in m and (not flag):
			m.add(el)
			if len(m) == 3:
				flag = True
		elif not el in m and flag:
			step += 1
			m = set()
			m.add(el)
			flag = False
	print(step)


t = int(input())
for _ in range(t):
	s = input()
	dc = set()
	res = 0
	ans = 0
	for i in s:
		if i not in dc:
			dc.add(i)
		if len(dc) == 4:
			ans += 1
			dc.clear()
			dc.add(i)
	if len(dc):
		ans += 1
	print(ans)


x = int(input())
for i in range(x):
	a = input()
	l = []
	day = 1
	for j in a:
		if j not in l:
			if len(l) == 3:
				l = [j]
				day += 1
			else:
				l.append(j)
	print(day)


for _ in range(int(input())):
	s = input()
	st = set()
	ans = 0
	for i in s:
		st.add(i)
		if len(st) > 3:
			st = set()
			st.add(i)
			ans += 1
	ans += 1
	print(ans)


n = int(input())
for i in range(n):
	x = input()
	l = list(x)
	l1 = []
	count = 0
	for i in l:
		if i not in l1:
			l1.append(i)
			if len(l1) == 4:
				l1.clear()
				l1.append(i)
				count += 1
	if len(l1) <= 3 and len(l1) > 0:
		count += 1
	print(count)


t = int(input())
for i in range(t):
	s = input()
	ans = 1
	d = {}
	for c in s:
		if c in d:
			continue
		if len(d) < 3:
			d[c] = 1
		else:
			ans += 1
			d = {c: 1}
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	st = set()
	ans = 1
	for c in s:
		st.add(c)
		if len(st) > 3:
			st = set()
			st.add(c)
			ans += 1
	print(ans)


def int_input():
	a = int(input())
	return a

def int_list_input():
	a = list(map(int, input().split()))
	return a

def solve():
	s = input()
	ans = 1
	d = {}
	for i in s:
		if i in d:
			continue
		if len(d) >= 3:
			d = {}
			ans += 1
		d[i] = 0
	print(ans)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	line = input()
	days = 1
	memory = []
	for char in line:
		if char not in memory:
			if len(memory) < 3:
				memory.append(char)
			else:
				memory = [char]
				days += 1
	print(days)


t = int(input())
for i in range(t):
	a = input()
	b = set()
	cnt = 0
	for j in a:
		b.add(j)
		if len(b) > 3:
			cnt += 1
			b = {j}
	print(cnt + 1)


t = int(input())

def pwsm(w):
	dic = {}
	distcount = 0
	daycount = 0
	for i in w:
		if not dic.get(i, 0):
			distcount += 1
			dic[i] = 1
		if distcount == 4:
			daycount += 1
			dic = {}
			dic[i] = 1
			distcount = 1
	if distcount > 0:
		daycount += 1
	return daycount
for i in range(t):
	s = input()
	ans = pwsm(s)
	print(ans)


for i in range(int(input())):
	(cs, cnt) = ([], 1)
	for c in input():
		if c in cs:
			continue
		if len(cs) == 3:
			cs = [c]
			cnt += 1
		else:
			cs.append(c)
	print(cnt)


import sys
T = int(sys.stdin.readline())
for t in range(T):
	s = sys.stdin.readline().rstrip()
	answer = 1
	memory = set()
	for ch in s:
		if ch in memory:
			continue
		elif len(memory) == 3:
			memory.clear()
			memory.add(ch)
			answer += 1
		else:
			memory.add(ch)
	print(answer)


t = int(input())
for _ in range(t):
	s = input()
	days = 1
	memory = set()
	for c in s:
		if c in memory:
			continue
		elif len(memory) < 3:
			memory.add(c)
		else:
			memory = set(c)
			days += 1
	print(days)


t = int(input())
for i in range(t):
	string = str(input())
	h = 0
	dicts = {}
	for s in string:
		dicts[s] = 1
		if len(dicts) == 4:
			h += 1
			dicts = {}
			dicts[s] = 1
	print(h + 1)


t = int(input())
for i in range(t):
	st = input()
	days = 0
	memory = []
	for i in st:
		if len(memory) == 3 and i not in memory:
			days += 1
			memory = []
		if i not in memory:
			memory.append(i)
	if len(memory) > 0:
		days += 1
	print(days)


for s in [*open(0)][1:]:
	t = set()
	i = 1
	for x in s[:-1]:
		if len((t := (t | {x}))) > 3:
			t = {x}
			i += 1
	print(i)


for _ in range(int(input())):
	word = input()
	days = 1
	memory = set()
	for l in word:
		memory.add(l)
		if len(memory) > 3:
			memory.clear()
			memory.add(l)
			days += 1
	print(days)


for _ in range(int(input())):
	s = input()
	n = len(s)
	count = 0
	day = 0
	ll = ''
	for i in s:
		if i not in ll:
			ll += i
			count += 1
		if count == 4:
			ll = i
			count = 1
			day += 1
	if count > 0:
		day += 1
	print(day)


t = int(input())
for j in range(0, t):
	s = input()
	arr = []
	day = 0
	for c in s:
		if c not in arr:
			if len(arr) == 3:
				day += 1
				arr = []
			arr.append(c)
	day += 1
	print(day)


for _ in range(int(input())):
	s = input()
	a = set()
	res = 1
	for i in s:
		if not i in a and len(a) == 3:
			a = set()
			res += 1
		a.add(i)
	print(res)


for _ in range(int(input())):
	s = input()
	ms = set()
	ans = 0
	for i in s:
		ms.add(i)
		if len(ms) > 3:
			ans += 1
			ms = set()
			ms.add(i)
	print(ans if not len(ms) else ans + 1)


i = input()
for n in range(int(i)):
	str = input()
	l = []
	count = 1
	for c in str:
		if not c in l:
			if len(l) == 3:
				count += 1
				l = []
			l.append(c)
	print(count)


def exe():
	su = 0
	d = {}
	for i in s:
		d[i] = 0
		if len(d) == 4:
			d = {}
			d[i] = 0
			su += 1
	su += 1
	return su
for i in range(int(input())):
	s = input()
	print(exe())


def solve():
	n = input()
	res = 0
	s = set()
	for i in n:
		if i in s:
			continue
		if len(s) == 3:
			s.clear()
			res += 1
		s.add(i)
	print(res + 1)
	return

def main():
	for _ in range(int(input())):
		solve()
	return
main()


t = int(input())
for _ in range(t):
	s = input()
	chars = set()
	ans = 0
	for char in s:
		chars.add(char)
		if len(chars) > 3:
			chars = set()
			chars.add(char)
			ans += 1
	if len(chars) > 0:
		ans += 1
	print(ans)


out = []
for _ in range(int(input())):
	s = input()
	ans = 1
	difs = set()
	for i in s:
		if not i in difs:
			difs.add(i)
			if len(difs) > 3:
				ans += 1
				difs = set(i)
	out.append(ans)
for i in out:
	print(i)


from math import ceil
for _ in range(int(input())):
	s = input()
	d = {}
	ans = 0
	for i in s:
		if i in d:
			continue
		elif len(d) == 3:
			ans += 1
			d = {}
		d[i] = 1
	if len(d) != 0:
		ans += 1
	print(ans)


for _ in range(int(input())):
	m = input()
	cur = []
	res = 0
	for i in range(len(m)):
		if m[i] not in cur:
			if len(cur) == 3:
				res += 1
				cur = []
			cur.append(m[i])
	if len(cur) != 0:
		res += 1
	print(res)


n = int(input())
for i in range(n):
	s = input()
	a = 1
	mem = []
	for i in s:
		if not i in mem and len(mem) < 3:
			mem.append(i)
		elif not i in mem:
			mem = [i]
			a += 1
	print(a)


for _ in range(int(input())):
	i = input()
	new = 0
	s = {}
	days = 0
	for x in i:
		if x not in s:
			if new == 3:
				days += 1
				s = {}
				new = 0
			s[x] = 1
			new += 1
	print(days + 1)


for _ in range(int(input())):
	s = input()
	c = 1
	n = len(s)
	x = set()
	for i in s:
		x.add(i)
		if len(x) > 3:
			x = {i}
			c += 1
	print(c)


def main():
	length = int(input())
	for _ in range(length):
		string = input()
		ans = solver(string)
		print(ans)

def solver(string):
	n = len(string)
	word_dict = set()
	ans = 1
	for i in range(n):
		if string[i] in word_dict:
			continue
		else:
			if len(word_dict) >= 3:
				ans += 1
				word_dict = set()
			word_dict.add(string[i])
	return ans
main()


def solve(s):
	n = len(s)
	learnt = set()
	i = 0
	days = 1
	while i < n:
		if len(learnt) == 3 and s[i] not in learnt:
			days += 1
			learnt.clear()
			learnt.add(s[i])
			i += 1
			continue
		elif s[i] in learnt:
			i += 1
			continue
		else:
			learnt.add(s[i])
			i += 1
	return days

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


t = int(input())
for i in range(t):
	s = input()
	a = []
	n = 1
	for i in range(len(s)):
		if s[i] not in a:
			if len(a) == 3:
				n += 1
				a = [s[i]]
			else:
				a.append(s[i])
	print(n)


for tc in range(int(input())):
	s = input()
	hp = set()
	ans = 0
	for i in range(len(s)):
		hp.add(s[i])
		if len(hp) == 4:
			ans += 1
			hp.clear()
			hp.add(s[i])
	if len(hp) > 0:
		ans += 1
	print(ans)


for _ in range(int(input())):
	s = input()
	ans = 0
	x = set()
	for a in s:
		if a not in x:
			x.add(a)
			if len(x) > 3:
				ans += 1
				x = set([a])
	if len(x):
		ans += 1
	print(ans)


t = int(input().strip())
for _ in range(t):
	s = input().strip()
	days = 1
	letter_count = 0
	lst = []
	for c in s:
		if letter_count < 3 and c not in lst:
			lst.append(c)
			letter_count += 1
		elif letter_count <= 3 and c in lst:
			lst.append(c)
		else:
			days += 1
			lst.clear()
			lst.append(c)
			letter_count = 1
	print(days)


t = int(input())
ans = []
for i in range(t):
	n = input()
	lst = []
	day = 0
	for j in n:
		if j not in lst:
			lst.append(j)
		if len(lst) == 4:
			lst = []
			lst.append(j)
			day += 1
	if len(lst) != 0:
		ans.append(day + 1)
	else:
		ans.append(day)
for i in ans:
	print(i)


import math
test = int(input())
for t in range(test):
	s = input()
	mem = set()
	day = 1
	for c in s:
		if c not in mem:
			if len(mem) < 3:
				mem.add(c)
			else:
				day += 1
				mem = set()
				mem.add(c)
		else:
			pass
	print(day)


for i in range(int(input())):
	a = input()
	c = set()
	res = 0
	for j in a:
		if j in c:
			c.add(j)
		elif len(c) == 3:
			res += 1
			c = set()
		c.add(j)
	if len(c) > 0:
		res += 1
	print(res)


t = int(input())
while t:
	s = input()
	no_of_days = 1
	str_day = ''
	for i in s:
		if i not in str_day:
			if len(str_day) < 3:
				str_day = str_day + i
			else:
				no_of_days = no_of_days + 1
				str_day = i
	print(no_of_days)
	t = t - 1


from math import ceil
cases = int(input())
for _ in range(cases):
	n = input()
	if len(n) == 0:
		print(0)
		continue
	remembered = set()
	day = 1
	for i in n:
		if i in remembered:
			continue
		elif len(remembered) < 3:
			remembered.add(i)
		else:
			day += 1
			remembered = set(i)
	print(day)


targs = int(input())
for _ in range(targs):
	newstr = input()
	days = 1
	chars = set()
	newchars = 0
	for ch in newstr:
		if ch not in chars:
			if len(chars) == 3:
				chars = set()
				days += 1
			chars.add(ch)
	print(days)


t = int(input())

def f(n):
	k = n[0]
	l = [k]
	L = []
	for i in range(len(n)):
		if len(l) != 3 and n[i] not in l:
			l.append(n[i])
			k = n[i]
		elif len(l) == 3 and n[i] not in l:
			L.append(l)
			l = [n[i]]
	return len(L) + 1
for i in range(t):
	n = input()
	print(f(n))


n = int(input())
for i in range(n):
	line = input()
	apha = []
	day = 0
	count = 0
	for i in line:
		if i not in apha:
			if count == 3:
				day = day + 1
				apha = []
				count = 0
			apha.append(i)
			count = count + 1
		else:
			pass
	if day >= 0 and count > 0:
		day = day + 1
	print(day)


def writes_st(arr):
	resp = 1
	brr = []
	for item in arr:
		if item not in brr:
			if len(brr) == 3:
				resp += 1
				brr = [item]
			else:
				brr.append(item)
	return resp
t = int(input())
for _ in range(0, t):
	st = input()
	arr = list(st)
	response = writes_st(arr)
	print(f'{response}')


n = int(input())
for i in range(n):
	stroka = input()
	massiv = []
	otvet = 0
	ans = 0
	for j in stroka:
		if otvet == 3 and j not in massiv:
			ans += 1
			massiv = []
			otvet = 0
			massiv.append(j)
			otvet += 1
			continue
		if j not in massiv:
			otvet += 1
		massiv.append(j)
	print(ans + 1)


t = int(input())
for x in range(t):
	word = input()
	checkSet = set()
	cnt = 0
	for i in word:
		checkSet.add(i)
		if len(checkSet) > 3:
			checkSet = set()
			cnt += 1
			checkSet.add(i)
	if len(checkSet) > 0:
		cnt += 1
	print(cnt)


t = int(input())
for i in range(t):
	s = input()
	p = []
	ans = 0
	for j in range(len(s)):
		if s[j] in p:
			pass
		elif len(p) == 3:
			p = [s[j]]
			ans += 1
		else:
			p.append(s[j])
	if p:
		ans += 1
	print(ans)


case = int(input())
for i in range(case):
	x = input()
	ans = 0
	sublist = []
	for j in range(len(x)):
		if x[j] not in sublist:
			if len(sublist) == 3:
				ans += 1
				sublist = []
				sublist.append(x[j])
			else:
				sublist.append(x[j])
		else:
			pass
	if len(sublist) > 0:
		ans += 1
	print(ans)


from math import ceil
t = int(input())
for _ in range(t):
	s = input()
	foo = [s[0]]
	cnt = 0
	for el in s[1:]:
		if el in foo[-3:]:
			continue
		else:
			if len(foo) == 3:
				cnt += 1
				foo = []
			foo.append(el)
	print(cnt + 1)