Polycarp likes numbers that are divisible by 3.

He has a huge number $s$. Polycarp wants to cut from it the maximum number of numbers that are divisible by $3$. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after $m$ such cuts, there will be $m+1$ parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by $3$.

For example, if the original number is $s=3121$, then Polycarp can cut it into three parts with two cuts: $3|1|21$. As a result, he will get two numbers that are divisible by $3$.

Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.

What is the maximum number of numbers divisible by $3$ that Polycarp can obtain?


-----Input-----

The first line of the input contains a positive integer $s$. The number of digits of the number $s$ is between $1$ and $2\cdot10^5$, inclusive. The first (leftmost) digit is not equal to 0.


-----Output-----

Print the maximum number of numbers divisible by $3$ that Polycarp can get by making vertical cuts in the given number $s$.


-----Examples-----
Input
3121

Output
2

Input
6

Output
1

Input
1000000000000000000000000000000000

Output
33

Input
201920181

Output
4



-----Note-----

In the first example, an example set of optimal cuts on the number is 3|1|21.

In the second example, you do not need to make any cuts. The specified number 6 forms one number that is divisible by $3$.

In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and $33$ digits 0. Each of the $33$ digits 0 forms a number that is divisible by $3$.

In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers $0$, $9$, $201$ and $81$ are divisible by $3$.

Source: codeforces | Difficulty: MEDIUM
Tags: Number theory

Dynamic programming

Greedy algorithms


Solutions:
def solve(s2):
	dp = [0] * (len(s2) + 1)
	for i in range(len(s2)):
		dp[i + 1] = dp[i]
		if i > 0 and int(s2[i] + s2[i - 1]) % 3 == 0:
			dp[i + 1] = max(dp[i + 1], 1 + dp[i - 1])
		if i > 1 and int(s2[i] + s2[i - 1] + s2[i - 2]) % 3 == 0:
			dp[i + 1] = max(dp[i + 1], 1 + dp[i - 2])
	return dp[-1]
s = list(map(int, input()))
ans = 0
s2 = ''
for c in s:
	if c % 3 == 0:
		ans += solve(s2)
		ans += 1
		s2 = ''
	else:
		s2 += str(c % 3)
ans += solve(s2)
print(ans)


import array
s = input()
p = array.array('i', [])
su = array.array('i', [])
for i in range(len(s) + 2):
	p.append(0)
	su.append(0)
i = 1
while i <= len(s):
	p[i] = p[i - 1] + int(s[i - 1])
	i += 1
i = len(s)
while i > 0:
	su[i] = su[i + 1] + int(s[i - 1])
	i -= 1
cnt = 0
l = 0
t_sum = p[len(s)]
for i in range(len(s) + 1):
	j = l
	while j < i:
		sum = t_sum - (p[j] + su[i + 1])
		if sum % 3 == 0:
			l = i
			cnt += 1
			break
		j += 1
print(cnt)


s = input()
l = []
n = len(s)
for i in range(n):
	l.append(int(s[i]))
for i in range(n):
	l[i] = l[i] % 3
d = {1: 0, 2: 0, 0: 0}
cs = 0
for i in range(n):
	if l[i] == 0:
		cs += 1
		(d[0], d[1], d[2]) = (0, 0, 0)
		i += 1
	elif l[i] == 1:
		d[1] += 1
		if d[1] % 3 == 0 or d[2] != 0:
			cs += 1
			(d[1], d[2]) = (0, 0)
	else:
		d[2] += 1
		if 2 * d[2] % 3 == 0 or d[1] != 0:
			cs += 1
			(d[1], d[2]) = (0, 0)
print(cs)


import sys, os
from io import BytesIO, IOBase
import collections, itertools, bisect, heapq, math, string
from decimal import *
BUFSIZE = 8192
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	s = str(input())
	m = []
	for i in range(len(s)):
		m.append(int(s[i]) % 3)
	ans = 0
	(l, r) = (0, 0)
	t = 0
	while l < len(m):
		mod = set([0])
		while r < len(m):
			t = t + m[r]
			if t % 3 in mod or m[r] == 0:
				t = 0
				ans += 1
				r = r + 1
				mod = set([0])
				break
			mod.add(t % 3)
			r = r + 1
		l = r
	print(ans)
main()


def main():
	a = b = res = 0
	for c in map({'0': 0, '1': 1, '2': 2, '3': 0, '4': 1, '5': 2, '6': 0, '7': 1, '8': 2, '9': 0}.get, input()):
		if not c:
			res += 1
			a = b = 0
		elif c == 1:
			if a == 2 or b == 1:
				res += 1
				a = b = 0
			elif a:
				b = 1
			else:
				a = 1
		elif a == 1 or b == 1:
			res += 1
			a = b = 0
		elif a:
			b = 1
		else:
			a = 2
	print(res)
main()


s = input()
n = len(s)
sum = 0
cnt = 0
ans = 0
for i in range(n):
	digit = int(s[i])
	sum += digit
	cnt += 1
	if digit % 3 == 0 or sum % 3 == 0 or cnt == 3:
		sum = 0
		cnt = 0
		ans += 1
print(ans)


s = input()
n = len(s)
dp = []
res = 0
for e in range(n):
	num = int(s[e])
	if num % 3 == 0:
		dp = []
		res += 1
		continue
	flag = True
	for i in range(len(dp)):
		dp[i] += num
		if dp[i] % 3 == 0:
			dp = []
			res += 1
			flag = False
			break
	if flag:
		dp.append(num)
print(res)


s = input()
fin = [0, -1, -1]
z = [0 for i in range(len(s) + 1)]
r = 0
for i in range(1, len(s) + 1):
	r = (r + int(s[i - 1])) % 3
	z[i] = z[i - 1]
	if fin[r] != -1:
		z[i] = max(z[i], z[fin[r]] + 1)
	fin[r] = i
print(z[len(s)])


s = input()
n = len(s)
ans = 0
i = 0
while i < n:
	if int(s[i]) % 3 == 0:
		ans += 1
		i += 1
		continue
	if i != n - 1 and int(s[i]) % 3 == 1 and (int(s[i + 1]) % 3 == 2):
		ans += 1
		i += 2
		continue
	if i != n - 1 and int(s[i]) % 3 == 2 and (int(s[i + 1]) % 3 == 1):
		ans += 1
		i += 2
		continue
	if i < n - 2 and int(s[i]) % 3 == int(s[i + 1]) % 3 == int(s[i + 2]) % 3 == 1:
		ans += 1
		i += 3
		continue
	if i < n - 2 and int(s[i]) % 3 == int(s[i + 1]) % 3 == int(s[i + 2]) % 3 == 2:
		ans += 1
		i += 3
		continue
	i += 1
print(ans)


s = input()
ans = 0
stack = ''
revStack = ''
cursor = 0
for e in s:
	if e == '0':
		ans += 1
		stack = ''
	elif int(e) % 3 == 0:
		ans += 1
		stack = ''
	else:
		stack += e
		if int(stack) % 3 == 0:
			ans += 1
			stack = ''
		elif len(stack) > 2:
			cursor = -1
			revStack = ''
			while -cursor < len(stack):
				revStack = stack[cursor] + revStack
				if int(revStack) % 3 == 0:
					ans += 1
					stack = ''
print(ans)


s = input().strip()
n = len(s)
z = [0 for _ in range(n + 1)]
cum = 0
prev = {}
for i in range(1, n + 1):
	x = int(s[i - 1])
	cum = (cum * 10 + x) % 3
	j = prev.get(cum)
	if j is None:
		z[i] = max(z[i - 1], 1 if cum == 0 else 0)
		prev[cum] = i
	else:
		z[i] = max(z[i - 1], z[j] + 1)
		prev[cum] = i
print(z[n])


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def prime_factors(n):
	factors = set()
	num = 0
	while n % 2 == 0:
		num += 1
		n //= 2
	if num:
		factors.add(2)
	i = 3
	while n > 1 and i * i <= n:
		num = 0
		while n % i == 0:
			num += 1
			n //= i
		if num:
			factors.add(i)
		i += 2
	if n > 2:
		factors.add(n)
	return factors

def solve():
	S = [int(s) for s in input()]
	pref = [0]
	curr = 0
	for j in range(len(S)):
		curr += S[j]
		curr %= 3
		pref.append(curr)
	dp = [0] * (len(S) + 1)
	prev = {0: 0, 1: -1, 2: -1}
	for j in range(1, len(S) + 1):
		dp[j] = dp[j - 1]
		ops = [prev[0], prev[1], prev[2]]
		for y in range(3):
			if pref[j] == y and prev[y] >= 0:
				dp[j] = max(dp[j], dp[ops[y]] + 1)
		prev[pref[j]] = j
	return dp[len(S)]
print(solve())


s = input()
sumarr = [int(s[0])]
for i in range(1, len(s)):
	sumarr.append(sumarr[i - 1] + int(s[i]))
ansarr = [int(sumarr[0] % 3 == 0) for _ in range(len(s))]
for i in range(1, len(s)):
	ansarr[i] = ansarr[i - 1]
	j = 1
	while i >= j and (sumarr[i] - sumarr[i - j]) % 3:
		j += 1
	if j <= i:
		ansarr[i] = max(ansarr[i], ansarr[i - j] + 1)
	elif sumarr[i] % 3 == 0:
		ansarr[i] = max(ansarr[i], 1)
print(ansarr[len(s) - 1])


s = input()
DP = [-1] * len(s)
DP[0] = 0
if int(s[0]) % 3 == 0:
	DP[0] = 1
for i in range(1, len(s)):
	tot = 0
	for j in range(0, 3):
		if i - j < 0:
			break
		tot += int(s[i - j])
		res = int(bool(tot % 3 == 0))
		if i - j - 1 >= 0:
			res += DP[i - j - 1]
		DP[i] = max(DP[i], res)
print(DP[-1])


s = str(input())
n = len(s)
t = []
for c in s:
	c = int(c)
	t.append(c)
t = [x % 3 for x in t]
cum = [0] * (n + 1)
for i in range(n):
	cum[i + 1] = cum[i] + t[i]
	cum[i + 1] %= 3
from collections import defaultdict
d = defaultdict(lambda : 0)
ans = 0
for c in cum:
	if d[c] != 0:
		ans += 1
		d = defaultdict(lambda : 0)
		d[c] += 1
	else:
		d[c] += 1
print(ans)


import sys
from math import sqrt, log2
from collections import Counter
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = input()
ct = 0
i = 0
s = []
while i < len(n):
	if not int(n[i]) % 3:
		ct += 1
		s.clear()
	else:
		t = int(n[i]) % 3
		if 3 - t in s:
			ct += 1
			s.clear()
		else:
			s.append(t)
	if len(s) == 3:
		ct += 1
		s.clear()
	i += 1
print(ct)


def solve(digits):
	solutions = {}
	for (index, digit) in enumerate(digits):
		if digit % 3 == 0:
			solutions[index] = 1 + solutions.get(index - 1, 0)
		else:
			cand1 = solutions.get(index - 1, 0)
			cand2 = 0
			for start_index in range(index - 1, -1, -1):
				if sum(digits[start_index:index + 1]) % 3 == 0:
					cand2 = solutions.get(start_index - 1, 0) + 1
					break
			solutions[index] = max(cand1, cand2)
	return solutions[len(digits) - 1]
number = int(input())
digits = [int(x) for x in str(number)]
print(solve(digits))


from collections import Counter, OrderedDict
from itertools import permutations as perm
from fractions import Fraction
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
start = 0
a = gbs()
n = len(a)
ans = 0

def willEnd(i):
	global start, ans
	s = 0
	newStart = i + 1
	while i >= start:
		s += a[i]
		if s % 3 == 0:
			start = newStart
			ans += 1
			return True
		i -= 1
	return False
for i in range(n):
	willEnd(i)
print(ans)


s = input()
n = len(s)
l = [[0, 0, 0] for i in range(n)]
ans = 0
x = int(s[0]) % 3
if x == 0:
	ans += 1
else:
	l[0][x] = 1
for i in range(1, n):
	x = int(s[i]) % 3
	if x == 0:
		ans += 1
		continue
	if l[i - 1][3 - x] > 0:
		ans += 1
		l[i][3 - x] = 0
		l[i][x] = 0
	elif l[i - 1][x] != 0:
		l[i][1] = 1
		l[i][2] = 1
	else:
		l[i][x] = 1
print(ans)


s = input()
ost = []
for i in map(int, s):
	ost += [i % 3]
now = 0
last = -1
answer = 0
for i in ost:
	if i == 0:
		now = []
		answer += 1
	elif now == 2:
		now = 0
		answer += 1
	elif now == 1:
		if last != i:
			answer += 1
			now = 0
		else:
			now = 2
	else:
		now = 1
		last = i
print(answer)


s = input().strip()
i = 0
ans = 0
while i < len(s):
	rem_digits = len(s) - i
	if rem_digits >= 3:
		if int(s[i]) % 3 == 0:
			i += 1
		elif int(s[i:i + 2]) % 3 == 0:
			i += 2
		elif int(s[i + 1]) % 3 == 0:
			i += 2
		else:
			i += 3
		ans += 1
	elif rem_digits == 2:
		if int(s[i]) % 3 == 0:
			i += 1
			ans += 1
		elif int(s[i:i + 2]) % 3 == 0:
			i += 2
			ans += 1
		else:
			i += 1
	else:
		if int(s[i]) % 3 == 0:
			ans += 1
		i += 1
print(ans)


s = input()
(num, cnt, l) = (0, 0, 0)
for ch in s:
	(num, l) = (num + int(ch), l + 1)
	if num % 3 == 0 or l >= 3 or int(ch) % 3 == 0:
		(cnt, num, l) = (cnt + 1, 0, 0)
print(cnt)


MOD = 1000000007
MOD2 = 998244353
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
let = '@abcdefghijklmnopqrstuvwxyz'
s = si()
n = len(s)
l = [0] * n
rem = [-1] * 3
(rem[0], x) = (0, 0)
for i in range(n):
	x = (x + int(s[i])) % 3
	if rem[x] != -1:
		l[i] = max(l[i - 1], l[rem[x]] + 1)
	else:
		l[i] = l[i - 1]
	rem[x] = i
print(l[n - 1])


ls = [int(i) % 3 for i in input()]
ls.reverse()
cnt = 0
lst = 0
sub = 0
for i in ls:
	if i == 0 or lst + i == 3 or sub + i == 3:
		sub = 0
		lst = 0
		cnt += 1
	else:
		lst = (lst + i) % 3
		sub = i
print(cnt)


s = input()
ans = 0
k = 0
while k < len(s):
	sk = int(s[k])
	if sk % 3 != 0:
		if k + 1 == len(s):
			break
		else:
			sk2 = int(s[k + 1])
			if sk2 % 3 == sk % 3:
				if k + 2 == len(s):
					break
				else:
					k = k + 2
			else:
				k = k + 1
	ans = ans + 1
	k = k + 1
print(ans)


s = input()
n = len(s)
ans = 0
c = 0
l = []
for i in range(n):
	a = int(s[i]) % 3
	if a == 0:
		ans += 1
		c = 0
		l = []
	elif c == 0:
		l.append(int(s[i]))
		c += 1
	elif c == 1:
		if (a + l[0]) % 3 == 0:
			ans += 1
			c = 0
			l = []
		else:
			c += 1
	else:
		ans += 1
		c = 0
		l = []
print(ans)


(s, r, fin) = (input(), 0, [0, -1, -1])
n = len(s)
z = [0 for _ in range(n + 1)]
for (i, c) in enumerate(s):
	r = (r + int(c)) % 3
	z[i + 1] = z[i]
	if fin[r] != -1:
		z[i + 1] = max(z[i + 1], z[fin[r]] + 1)
	fin[r] = i + 1
print(z[n])


m = 1
r = s = 0
for c in input():
	s += int(c)
	b = 1 << s % 3
	if m & b:
		m = 0
		r += 1
	m |= b
print(r)


import sys
input = sys.stdin.readline
s = input()[:-1]
n = len(s)
dp = [0] * (n + 1)
acc = 0
d = {0: 0}
for i in range(n):
	acc += int(s[i])
	if acc % 3 in d:
		dp[i + 1] = max(dp[i], d[acc % 3] + 1)
	else:
		dp[i + 1] = dp[i]
	d[acc % 3] = dp[i + 1]
print(dp[n])


n = input()
l = len(n)
preSum = [0] * l
preSum[0] = int(n[0])
for i in range(1, l):
	preSum[i] = preSum[i - 1] + int(n[i])
dp = [0] * l
if preSum[0] % 3 == 0:
	dp[0] = 1
for i in range(1, l):
	dp[i] = dp[i - 1]
	if int(n[i]) % 3 == 0:
		dp[i] += 1
	else:
		for j in range(i - 1, -1, -1):
			nums = preSum[i] - preSum[j] + int(n[j])
			if nums % 3 == 0:
				if j > 0:
					dp[i] = max(dp[i], dp[j - 1] + 1)
				else:
					dp[i] = max(dp[i], 1)
				break
print(dp[l - 1])


n = input()
(ans, s, ans1) = (0, 0, 0)
for i in n:
	s += int(i)
	ans1 += 1
	if int(i) % 3 == 0 or ans1 % 3 == 0 or s % 3 == 0:
		ans1 = 0
		s = 0
		ans += 1
print(ans)


s = input()
z = 0
t = ''
for i in range(len(s)):
	if s[i] == '0' or int(s[i]) % 3 == 0:
		z += 1
		t += '0'
	else:
		t += s[i]
a = t.split('0')
num = 0
for i in range(len(a)):
	mod = -1
	q = 0
	for j in range(len(a[i])):
		k = int(a[i][j])
		if mod == -1:
			mod = k % 3
			q += 1
		else:
			mod += k % 3
			q += 1
		if mod % 3 == 0:
			num += 1
			mod = -1
			q = 0
		elif q == 3:
			num += 1
			mod = -1
			q = 0
print(z + num)


s = input()
a = list()
for item in s:
	ele = int(item)
	a.append(ele)
n = len(s)
for i in range(n):
	a[i] = a[i] % 3
one = 0
two = 0
ans = 0
for i in range(n):
	if a[i] == 1:
		one += 1
	elif a[i] == 2:
		two += 1
	else:
		one = 0
		two = 0
		ans += 1
		continue
	if one and two:
		ans += 1
		one = 0
		two = 0
	elif one == 3 and two == 0:
		ans += 1
		one = 0
		two = 0
	elif two == 3 and one == 0:
		ans += 1
		one = 0
		two = 0
print(ans)


R = lambda : map(int, input().split())
arr = [int(x) for x in input()]
(l, cnt) = (-1, 0)
for i in range(len(arr)):
	j = i
	num = 0
	while j > l:
		num = 10 * num + arr[j]
		if num % 3 == 0:
			cnt += 1
			l = i
			break
		j -= 1
print(cnt)


import math
from collections import defaultdict
from sys import stdin, stdout

def main():
	a = list(map(int, list(input())))
	n = len(a)
	dp = [0] * (n + 1)
	rem = 0
	latest_mod_index = [-1] * 3
	latest_mod_index[0] = 0
	for i in range(1, n + 1):
		rem = (rem + a[i - 1]) % 3
		dp[i] = dp[i - 1]
		if latest_mod_index[rem] != -1:
			dp[i] = max(dp[i], dp[latest_mod_index[rem]] + 1)
		latest_mod_index[rem] = i
	print(dp[n])
main()


s = [int(i) % 3 for i in input()]
prev = 0
twice = 0
count = 0
for i in s:
	if i == 0:
		count += 1
		twice = 0
		prev = 0
	if i == 1:
		if prev == 2 or twice == 1:
			count += 1
			twice = 0
			prev = 0
		elif prev == 0:
			prev = 1
		else:
			twice = 1
	if i == 2:
		if prev == 1 or twice == 1:
			count += 1
			twice = 0
			prev = 0
		elif prev == 0:
			prev = 2
		else:
			twice = 1
print(count)


num = input()
curr = 0
ans = 0
for i in range(len(num)):
	curr += int(num[i])
	if curr % 3 == 0:
		ans += 1
		curr = 0
	elif int(num[i]) % 3 == 0:
		ans += 1
		curr = 0
	elif i < len(num) - 1:
		if (int(num[i]) + int(num[i + 1])) % 3 == 0:
			curr = int(num[i])
print(ans)


s = input()
l = len(s)
c = 0
k = 0
z = 0
for i in range(l):
	c += int(s[i])
	z += 1
	if c % 3 == 0 or int(s[i]) % 3 == 0 or z % 3 == 0:
		c = 0
		z = 0
		k += 1
print(k)


s = list(map(int, input()))
summods = [None] * len(s)
summods[0] = s[0] % 3
for i in range(1, len(s)):
	summods[i] = (summods[i - 1] + s[i]) % 3
nextsamemod = [None] * len(s)
nxts = [None, None, None]
for i in range(len(s) - 1, -1, -1):
	nextsamemod[i] = nxts[summods[i]]
	nxts[summods[i]] = i
t = [None] * len(s)
first0 = None
for i in range(len(s)):
	if summods[i] == 0:
		first0 = i
		break
jumpto = [first0] + nextsamemod[:-1]
t[-1] = 1 if s[-1] % 3 == 0 else 0
for i in range(len(s) - 2, -1, -1):
	if jumpto[i] is not None:
		if jumpto[i] + 1 >= len(s):
			t[i] = max(t[i + 1], 1)
		else:
			t[i] = max(t[i + 1], 1 + t[jumpto[i] + 1])
	else:
		t[i] = t[i + 1]
print(t[0])


s = input()
n = len(s)
ans = 0
sum = 0
num = 0
cur = 0
for i in range(n):
	num = int(s[i])
	if num % 3 == 0:
		ans += 1
		sum = 0
		cur = i
		continue
	sum += num
	if sum % 3 == 0:
		ans += 1
		sum = 0
		cur = i
		continue
	if i == cur + 3:
		ans += 1
		cur = i
		sum = 0
		continue
print(ans)


n = input()
(ans, out, s) = (0, 0, 0)
for x in n:
	s += int(x)
	ans += 1
	if int(x) % 3 == 0 or ans % 3 == 0 or s % 3 == 0:
		out += 1
		ans = 0
		s = 0
print(out)


s = input()
cursum = 0
curstr = ''
count = 0
for i in s:
	cursum += int(i)
	curstr += i
	if cursum % 3 == 0 or i in ['0', '3', '6', '9'] or (len(curstr) > 1 and int(curstr[1:]) % 3 == 0):
		count += 1
		cursum = 0
		curstr = ''
print(count)


l = list(input())
l = list(map(int, l))
fin = [0, -1, -1]
z = 0
dp = [0] * (len(l) + 1)
for i in range(1, len(l) + 1):
	z = (z + l[i - 1]) % 3
	dp[i] = dp[i - 1]
	if fin[z] != -1:
		dp[i] = max(dp[i], dp[fin[z]] + 1)
	fin[z] = i
print(dp[len(l)])


c = 0
r = 0
b = 0
for i in input():
	n = int(i) % 3
	if n == 0 or (n + r) % 3 == 0 or b == 2:
		c += 1
		r = 0
		b = 0
	else:
		r += n
		b += 1
print(c)


S = list(map(int, input()))
SHORTEST = [0 for i in range(len(S) + 1)]
for i in range(1, len(S) + 1):
	SUM = 0
	for j in range(i, len(S) + 1):
		SUM += S[j - 1]
		if SUM % 3 == 0:
			SHORTEST[j] = min(j - i + 1, SHORTEST[j]) if SHORTEST[j] > 0 else j - i + 1
			break
DP = [0 for i in range(len(S) + 1)]
for i in range(1, len(S) + 1):
	div3 = 1 if S[i - 1] % 3 == 0 else 0
	DP[i] = max(DP[i - 1] + div3, DP[i - SHORTEST[i]] + 1) if SHORTEST[i] > 0 else DP[i - 1] + div3
print(DP[len(S)])


import os
import sys
from io import BytesIO, IOBase

def main():
	a = list(map(int, input().rstrip()))
	(b, su, n) = ([0, -1, -1], 0, len(a))
	dp = [0] * (n + 1)
	for i in range(1, n + 1):
		su = (su + a[i - 1]) % 3
		dp[i] = dp[i - 1]
		if b[su] != -1:
			dp[i] = max(dp[i], dp[b[su]] + 1)
		b[su] = i
	print(max(dp))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import Counter
s = input()
ans = 0
t = 0
count = 0
for y in s:
	x = int(y)
	count += 1
	t += x
	if count % 3 == 0 or x % 3 == 0 or t % 3 == 0:
		ans += 1
		count = 0
		t = 0
print(ans)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_right
s = list(map(int, list(input())))
for i in range(len(s)):
	s[i] = s[i] % 3
count = 0
z = 0
prev = 0
for i in s:
	if i == 0:
		count += 1
		prev = 0
		z = 0
	elif i == 1:
		if prev == 0:
			z += i
			prev = i
		elif prev == 1:
			if (z + i) % 3 == 0:
				count += 1
				z = 0
				prev = 0
			else:
				z += i
				prev = 1
		else:
			count += 1
			z = 0
			prev = 0
	elif prev == 0:
		z += i
		prev = i
	elif prev == 1:
		count += 1
		prev = 0
		z = 0
	elif (z + i) % 3 == 0:
		count += 1
		z = 0
		prev = 0
	else:
		z += i
		prev = 2
print(count)


def main():
	ret = 0
	lst = [int(i) for i in input()]
	l = len(lst)
	ind = 0
	while ind < l:
		if lst[ind] % 3 == 0:
			ind += 1
			ret += 1
		elif l - ind >= 2 and ((lst[ind] + lst[ind + 1]) % 3 == 0 or lst[ind + 1] % 3 == 0):
			ret += 1
			ind += 2
		elif l - ind >= 3 and ((lst[ind] + lst[ind + 1] + lst[ind + 2]) % 3 == 0 or (lst[ind + 1] + lst[ind + 2]) % 3 == 0 or lst[ind + 2] % 3 == 0):
			ret += 1
			ind += 3
		else:
			break
	print(ret)
	return 0
main()


s = 0
str = input()
i = 0
sum = 0
while i < len(str):
	if int(str[i]) % 3 == 0:
		sum = 0
		s += 1
	else:
		sum += int(str[i]) % 3
		if sum in [3, 5, 6]:
			sum = 0
			s += 1
		elif sum == 4 and int(str[i]) % 3 != int(str[i - 1]) % 3:
			sum = 0
			s += 1
	i += 1
print(s)


s = input()
total = 0
solution = 0
length = len(s)
count = 0
for i in range(length):
	num = int(s[i])
	if count == 2:
		solution += 1
		total = 0
		count = 0
	elif num % 3 == 0:
		solution += 1
		total = 0
		count = 0
	else:
		total += num
		if total % 3 == 0:
			solution += 1
			total = 0
			count = 0
		else:
			count += 1
print(solution)


s = str(input())
n = len(s)
l = [-1] * 3
a = []
pre = [0]
dp = [int(0)] * n
for i in range(len(s)):
	a.append(int(s[i]))
	pre.append((pre[i] + int(s[i])) % 3)
dp[n - 1] = a[n - 1] % 3 == 0
l[pre[n - 1]] = n - 1
l[pre[n]] = n
for i in range(n - 2, -1, -1):
	dp[i] = dp[i + 1] + int(a[i] % 3 == 0)
	if l[pre[i]] != -1:
		idx = l[pre[i]]
		if idx < n:
			dp[i] = max(dp[i], dp[idx] + 1)
		else:
			dp[i] = max(dp[i], 1)
	l[pre[i]] = i
print(int(dp[0]))


res_plain = 0
res_1 = -200000
res_2 = -200000
s = input()
for c in s:
	if c in '147':
		(res_plain, res_1, res_2) = (res_2, res_plain, res_1)
	elif c in '258':
		(res_plain, res_1, res_2) = (res_1, res_2, res_plain)
	res_plain = max(res_1, res_2, res_plain + 1)
print(res_plain)


s = list(map(int, list(input())))
n = len(s)
d = [0] * (n + 1)
pre = [0, -1, -1]
cnt = 0
for i in range(1, n + 1):
	cnt += s[i - 1]
	d[i] = d[i - 1]
	j = cnt % 3
	if pre[j] != -1:
		d[i] = max(d[i], d[pre[j]] + 1)
	pre[j] = i
print(d[n])


def mi():
	return map(int, input().split())

def fun(s, l):
	cur = 0
	cnt = 0
	i = 0
	counts = [0] * 3
	while i < l:
		cur += s[i]
		cur %= 3
		if cur == 0:
			cnt += 1
			counts = [0] * 3
			cur = 0
		else:
			counts[cur] += 1
			cur = 0
		if counts[1] >= 1 and counts[2] >= 1 or counts[1] == 3 or counts[2] == 3:
			cnt += 1
			counts = [0] * 3
		i += 1
	return cnt
s = list(map(int, list(input())))
l = len(s)
print(fun(s, l))


dp = dict()
dp[0] = 0
dp[1] = -1000000000.0
dp[2] = -1000000000.0
s = input()
n = len(s)
sum = 0
ans = 0
for i in range(n):
	v = ord(s[i]) - ord('0')
	sum += v
	sum %= 3
	dp[sum] = max(dp[0], dp[1], dp[2], dp[sum] + 1)
	ans = max(ans, dp[sum])
print(ans)


from os import path
import sys, time
mod = int(1000000000.0 + 7)
from math import ceil, floor, gcd, log, log2, factorial, sqrt
from collections import defaultdict, Counter, OrderedDict, deque
from itertools import combinations, permutations
from string import ascii_lowercase, ascii_uppercase
from bisect import *
from functools import reduce
from operator import mul
maxx = float('inf')
I = lambda : int(sys.stdin.buffer.readline())
lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
S = lambda : sys.stdin.readline().strip('\n')
grid = lambda r: [lint() for i in range(r)]
localsys = 0
start_time = time.time()
nCr = lambda n, r: reduce(mul, range(n - r + 1, n + 1), 1) // factorial(r)

def ceill(n, x):
	return (n + x - 1) // x
T = 0

def solve():
	arr = list(map(int, S()))
	(s, cnt, ans) = (0, 0, 0)
	for i in arr:
		(s, cnt) = (s + i, cnt + 1)
		if i % 3 == 0 or cnt % 3 == 0 or s % 3 == 0:
			(s, cnt, ans) = (0, 0, ans + 1)
	print(ans)

def run():
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
run()
T = I() if T else 1
for _ in range(T):
	solve()
if localsys:
	print('\n\nTime Elased :', time.time() - start_time, 'seconds')


s = input()
n = len(s)
a = [int(i) % 3 for i in s]
ans = 0
f = 0
ff = 0
for i in range(n):
	if a[i] == 0:
		ans += 1
		f = 0
		ff = 0
	else:
		f += a[i]
		f %= 3
		if ff == 0:
			ff = a[i]
		elif f == 0 or ff == f:
			ans += 1
			f = 0
			ff = 0
print(ans)


s = input()
arr = [int(item) % 3 for item in s]
sumi = 0
ans = 0
for i in range(len(arr)):
	if arr[i] == 0:
		ans += 1
		sumi = 0
		continue
	else:
		sumi += arr[i]
		if sumi % 3 == 0:
			ans += 1
			sumi = 0
			continue
		elif sumi == 4:
			if i >= 1 and arr[i - 1] == 1:
				ans += 1
				sumi = 0
				continue
		elif sumi == 5:
			if i >= 1 and arr[i - 1] == 2:
				ans += 1
				sumi = 0
				continue
print(ans)


S = input()
dp = [0] * (len(S) + 1)
v = [0] * (len(S) + 1)
v[len(S)] = 1
for i in reversed(range(len(S))):
	dp[i] = dp[i + 1]
	Sint = int(S[i:i + 1])
	if Sint % 3 == 0:
		dp[i] = 1 + dp[i]
		v[i] = 1
	else:
		k = 1
		while v[i + k] == 0:
			Sint = int(S[i:i + 1 + k])
			if Sint % 3 == 0:
				dp[i] = 1 + dp[i]
				v[i] = 1
				break
			k = k + 1
print(dp[0])


s = list(input())
k = len(s) + 1
ans = 0
s = [' '] + s
p = []
for i in range(1, k):
	if int(s[i]) % 3 == 0:
		ans = ans + 1
		s[i] = ' '
for i in range(k):
	if s[i] == ' ':
		p = [0]
		q = set()
		q.add(0)
	elif (p[-1] + int(s[i])) % 3 in q:
		ans = ans + 1
		q = set()
		q.add(0)
		p = [0]
	else:
		q.add((p[-1] + int(s[i])) % 3)
		p.append(p[-1] + int(s[i]))
print(ans)


s = list(map(int, list(input())))
dp = [0] * len(s)
t = [-1, -1, -1]
k = 0
m = 0
for i in range(len(s)):
	k += s[i]
	r = -1
	if t[k % 3] != -1:
		r = dp[t[k % 3]]
	elif k % 3 == 0:
		r = 0
	dp[i] = max(m, r + 1)
	t[k % 3] = i
	m = max(m, dp[i])
print(dp[-1])


s = input()
total = 0

def hay3(s):
	s = s[::-1]
	i = 0
	for c in s:
		i += int(c)
		if i % 3 == 0:
			return True
	return False
var = ''
for c in s:
	if c in '0369':
		total += 1
		var = ''
	else:
		var += c
		if hay3(var):
			total += 1
			var = ''
print(total)


a = input()
s = 0
d = [0, 0, 0]
for i in range(len(a) - 1, -1, -1):
	z = int(a[i]) % 3
	if z == 0:
		d = [0, 0, 0]
		s += 1
		continue
	d[z] += 1
	if d[2] == 3:
		s += 1
		d = [0, 0, 0]
	elif d[1] >= 1 and d[2] >= 1:
		s += 1
		d = [0, 0, 0]
	elif d[1] == 3:
		s += 1
		d = [0, 0, 0]
print(s)


a = input()
f = [0 for _ in range(len(a) + 1)]
s = [0 for _ in range(len(a) + 1)]
last0 = 0
last1 = -1
last2 = -1
for i in range(1, len(a) + 1):
	s[i] = (s[i - 1] + int(a[i - 1])) % 3
	if s[i] == 0:
		if last0 != -1:
			f[i] = max(f[i - 1], f[last0] + 1)
		else:
			f[i] = f[i - 1]
		last0 = i
	if s[i] == 1:
		if last1 != -1:
			f[i] = max(f[i - 1], f[last1] + 1)
		else:
			f[i] = f[i - 1]
		last1 = i
	if s[i] == 2:
		if last2 != -1:
			f[i] = max(f[i - 1], f[last2] + 1)
		else:
			f[i] = f[i - 1]
		last2 = i
print(f[len(a)])


n = input()
ans = 0
(r, c) = (0, 0)
for i in n:
	r += int(i)
	c += 1
	if int(i) % 3 == 0 or r % 3 == 0 or c == 3:
		ans += 1
		(r, c) = (0, 0)
print(ans)


s = [int(x) % 3 for x in input()]
i = 0
ans = 0
n = len(s)
while i < n:
	if s[i] == 0:
		ans += 1
		i += 1
		continue
	if s[i] == 1:
		if i + 1 < n and s[i + 1] == 2:
			ans += 1
			i += 2
			continue
		if i + 2 < n and s[i + 1] == s[i + 2] == 1:
			ans += 1
			i += 3
			continue
	if s[i] == 2:
		if i + 1 < n and s[i + 1] == 1:
			ans += 1
			i += 2
			continue
		if i + 2 < n and s[i + 1] == s[i + 2] == 2:
			ans += 1
			i += 3
			continue
	i += 1
print(ans)


s = [int(i) for i in input()]
ans = 0
last = 0

def check(x):
	Sum = 0
	while x != 0:
		Sum += x % 10
		x //= 10
		if Sum % 3 == 0:
			return True
	return False
for i in range(len(s)):
	if s[i] % 3 == 0:
		ans += 1
		last = 0
	else:
		last = last * 10 + s[i]
		if check(last):
			ans += 1
			last = 0
print(ans)


t = 1
r = s = 0
for c in input():
	s = (s + int(c)) % 3
	if t >> s & 1:
		(r, s, t) = (r + 1, 0, 1)
	else:
		t |= 1 << s
print(r)


a = input().strip('\n')
count = 0
lenofsnake = 0
snaketotal = 0
for i in range(len(a)):
	if int(a[i]) % 3 == 0:
		count = count + 1
		lenofsnake = 0
		snaketotal = 0
	elif lenofsnake == 2 or (snaketotal + int(a[i])) % 3 == 0:
		count = count + 1
		lenofsnake = 0
		snaketotal = 0
	else:
		lenofsnake = lenofsnake + 1
		snaketotal = snaketotal + int(a[i])
print(count)


def solve(digits):
	solutions = {}
	fin = {0: 0}
	digit_sum = 0
	for (index, digit) in enumerate(digits):
		digit_sum += digit
		solutions[index] = solutions.get(index - 1, 0)
		if digit_sum % 3 in fin:
			solutions[index] = max(solutions[index], solutions.get(fin[digit_sum % 3], 0) + 1)
		fin[digit_sum % 3] = index
	return solutions[len(digits) - 1]
number = int(input())
digits = [int(x) for x in str(number)]
print(solve(digits))


n = list(input())
ans = 0
nowsum = 0
prev = '0'
for i in n:
	if i in ['0', '3', '6', '9']:
		ans += 1
		nowsum = 0
		prev = '0'
	elif (nowsum + int(i)) % 3 == 0:
		nowsum = 0
		ans += 1
		prev = '0'
	elif (int(prev) + int(i)) % 3 == 0:
		ans += 1
		nowsum = 0
		prev = '0'
	else:
		nowsum += int(i)
		prev = i
print(ans)


s = str(input())
arr = []
ans = 0
for i in range(len(s)):
	arr.append(int(s[i]) % 3)
i = 0
while i < len(arr):
	if arr[i] == 0:
		ans += 1
	elif i < len(arr) - 1 and (arr[i] == 1 and arr[i + 1] == 2 or (arr[i] == 2 and arr[i + 1] == 1)):
		ans += 1
		i += 1
	elif i < len(arr) - 2 and (arr[i] == 1 and arr[i + 1] == 1 and (arr[i + 2] == 1) or (arr[i] == 2 and arr[i + 1] == 2 and (arr[i + 2] == 2))):
		ans += 1
		i += 2
	i += 1
print(ans)


import sys
from itertools import accumulate

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
A = list(map(int, input()))
N = len(A)
A = [a % 3 for a in A]
ans = 0
S = set()
for a in A:
	if a == 0:
		ans += 1
		S = set()
	elif 3 - a in S:
		ans += 1
		S = set()
	else:
		if 1 in S:
			S.add((1 + a) % 3)
		if 2 in S:
			S.add((2 + a) % 3)
		S.add(a)
print(ans)


s = input()
j = 0
p = 0
q = ''
a = []
while j < len(s):
	if int(s[j]) % 3 == 0:
		p += 1
		a = []
	else:
		a.append(int(s[j]) % 3)
		if len(a) == 2 and sum(a) % 3 == 0:
			p += 1
			a = []
		elif len(a) == 3:
			p += 1
			a = []
	j += 1
print(p)


arr = input()
count = 0
idex = -1
for i in range(len(arr)):
	for j in range(i, idex, -1):
		next = int(arr[j:i + 1])
		if next % 3 == 0:
			idex = i
			count += 1
			break
print(count)


from queue import PriorityQueue
from queue import Queue
import math
from collections import *
import sys
import operator as op
s = input()
res = 0
i = 0
n = len(s)
pq = []
while i < n:
	if int(s[i]) % 3 == 0:
		res += 1
		pq = []
	else:
		fl = 0
		for g in range(len(pq)):
			pq[g] += int(s[i])
			if pq[g] % 3 == 0:
				res += 1
				fl = 1
				pq = []
				break
		if fl == 0:
			pq += [int(s[i])]
	i += 1
print(res)


import sys, math
from collections import defaultdict
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
s = input()
n = len(s)
a = [int(x) % 3 for x in s]
cut = [0] * (n + 1)
uncut = [set() for _ in range(n + 1)]
for (i, x) in enumerate(a):
	if x == 0:
		cut[i + 1] = cut[i] + 1
	else:
		cut[i + 1] = cut[i]
	ans = [-1, -1, -1]
	uncut[i + 1].add((x, cut[i]))
	for (a, b) in uncut[i]:
		ans[a] = max(ans[a], b)
	for j in range(3):
		if ans[j] == -1:
			continue
		now = (x + j) % 3
		if now == 0:
			cut[i + 1] = max(cut[i + 1], ans[j] + 1)
		else:
			uncut[i + 1].add((now, ans[j]))
res = cut[-1]
for (a, b) in uncut[-1]:
	res = max(res, b)
print(res)


s = input()
lastCut = 0
cpt = 0
for i in range(1, len(s) + 1):
	for k in range(i - lastCut):
		if i != lastCut and int(s[lastCut + k:i]) % 3 == 0 and (not (int(s[lastCut + k]) == 0 and len(s[lastCut + k:i]) != 1)):
			lastCut = i
			cpt += 1
print(cpt)


a = input()
count = 0
s = 0
ans = 0
for i in a:
	s += int(i)
	ans += 1
	if int(i) % 3 == 0 or ans % 3 == 0 or s % 3 == 0:
		s = 0
		ans = 0
		count += 1
print(count)


ch = input()
j = -1
ans = 0
for i in range(len(ch)):
	val = ord(ch[i]) - 48
	if val % 3 == 0:
		j = i
		ans += 1
		continue
	if i - j >= 2:
		val = (ord(ch[i - 1]) - 48) * 10 + ord(ch[i]) - 48
		if val % 3 == 0:
			j = i
			ans += 1
			continue
	if i - j >= 3:
		val = (ord(ch[i - 2]) - 48) * 100 + (ord(ch[i - 1]) - 48) * 10 + ord(ch[i]) - 48
		if val % 3 == 0:
			j = i
			ans += 1
			continue
print(ans)


s = list(map(int, input()))
cur = len(s) - 1
x = True
tmp = 0
ans = 0
while cur >= 0:
	tmp += s[cur] * x
	x *= 10
	if s[cur] == 0:
		ans += 1
		tmp = 0
		x = 1
	else:
		tmp2 = tmp
		while tmp2 != 0:
			if tmp2 % 3 == 0:
				ans += 1
				tmp = 0
				x = 1
				break
			tmp2 //= 10
	cur -= 1
print(ans)


import atexit, io, sys, collections, math, heapq, fractions, copy, os, functools
import sys
import random
import collections
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ais = list(map(int, list(input())))
bis = [ai % 3 for ai in ais]
mem = [[-1 for j in range(3)] for i in range(len(ais))]

def dfs(i, bis, ais, cumul):
	if i == len(bis):
		return 0
	if mem[i][cumul] != -1:
		return mem[i][cumul]
	if bis[i] == 0:
		t = 1 + dfs(i + 1, bis, ais, 0)
	else:
		aa = (1 if (cumul + bis[i]) % 3 == 0 else 0) + dfs(i + 1, bis, ais, (cumul + bis[i]) % 3)
		bb = dfs(i + 1, bis, ais, cumul)
		t = max(aa, bb)
	mem[i][cumul] = t
	return t
for i in range(len(ais) - 1, -1, -1):
	for val in [0, 1, 2]:
		dfs(i, bis, ais, val)
print(dfs(0, bis, ais, 0))


a = list(map(int, input()))
for i in range(len(a)):
	a[i] = a[i] % 3
s = 0
ans = 0
for i in range(len(a)):
	s += a[i]
	if a[i] == 0:
		s = 0
		ans += 1
	elif s % 3 == 0:
		s = 0
		ans += 1
	elif s != a[i] and abs(a[i] - a[i - 1]) == 1:
		s = 0
		ans += 1
print(ans)


import re
s = input()
s = re.sub('(3|6|9)', '0', s)
s = re.sub('(4|7)', '1', s)
s = re.sub('(5|8)', '2', s)
ans = s.count('0')
n = len(s)
s += '00'
i = 0
while i < n:
	if s[i] == '0':
		i += 1
	elif s[i + 1] == '0':
		i += 2
	elif s[i:i + 2] in ('12', '21'):
		ans += 1
		i += 2
	elif s[i + 2] == '0':
		i += 3
	elif s[i:i + 3] in ('111', '112', '221', '222'):
		ans += 1
		i += 3
print(ans)


s = input()
last_mod = [-1, -2, -2]
last_cut_end = -1
curr_sum = 0
answer = 0
for (i, c) in enumerate(s):
	curr_sum += int(c)
	residue = curr_sum % 3
	if last_mod[residue] >= last_cut_end:
		answer += 1
		last_cut_end = i
	last_mod[residue] = i
print(answer)


n = list(input())
cntr = 0
marks = []
for i in range(len(n)):
	marks.append(0)
for i in range(len(n)):
	if int(n[i]) % 3 == 0:
		cntr += 1
		marks[i] = 1
	elif marks[i] == 0:
		marks[i] = 1
		tmpcnt = int(n[i])
		mrk = -1
		for j in range(2):
			if i + j + 1 < len(n):
				if int(n[i + j + 1]) % 3 != 0:
					if (tmpcnt + int(n[i + j + 1])) % 3 == 0:
						cntr += 1
						mrk = i + j + 1
						break
					else:
						tmpcnt += int(n[i + j + 1])
				else:
					break
		if mrk != -1:
			for k in range(i + 1, mrk + 1):
				marks[k] = 1
print(cntr)


s = input()
count = 0
i = 0
while i < len(s):
	if int(s[i]) % 3 == 0:
		count += 1
		i += 1
	elif i < len(s) - 1 and (int(s[i:i + 2]) % 3 == 0 or int(s[i + 1]) % 3 == 0):
		count += 1
		i += 2
	elif i < len(s) - 2 and (int(s[i + 1:i + 3]) % 3 == 0 or int(s[i:i + 3]) % 3 == 0 or s[i + 2] == '0'):
		count += 1
		i += 3
	else:
		i += 1
print(count)


u = '0' + input()
n = len(u) - 1
d = [0] * (n + 1)

def div3(k):
	if int(k) % 3 == 0:
		return 1
	return 0
if div3(u[1]):
	d[1] = 1
else:
	d[1] = 0
for i in range(2, n + 1):
	a1 = d[i - 1] + div3(u[i])
	a2 = d[i - 2] + div3(u[i] + u[i - 1])
	if i > 2:
		a3 = d[i - 3] + div3(u[i] + u[i - 1] + u[i - 2])
	else:
		a3 = 0
	d[i] = max(a1, a2, a3)
print(d[-1])


s = input()
n = len(s)
ans = 0
num = 0
for i in range(n):
	if int(s[i]) % 3 == 0:
		ans += 1
		num = 0
	else:
		num += 1
		if num == 2 and (int(s[i]) + int(s[i - 1])) % 3 == 0 or num == 3:
			num = 0
			ans += 1
print(ans)


def main():
	s = list(map(int, list(input())))
	cnt = 0
	add = 0
	cnt_to_3 = 0
	for i in range(len(s)):
		add += s[i]
		cnt_to_3 += 1
		if s[i] % 3 == 0 or add % 3 == 0 or cnt_to_3 == 3:
			cnt += 1
			add = 0
			cnt_to_3 = 0
	print(cnt)
main()


T = input()
n = len(T)
i = 0
L = []
t = 0
while i < n:
	if int(T[i]) % 3 == 0:
		t += 1
		L = []
	else:
		L.append(int(T[i]) % 3)
		if L == [1, 1, 2] or L == [1, 1, 1] or L == [1, 2] or (L == [2, 1]) or (L == [2, 2, 1]) or (L == [2, 2, 2]):
			L = []
			t += 1
	i += 1
print(t)


s = input()
n = 0
ans = 0
for k in s:
	t = int(k)
	n += t
	if n % 3 == 0 or t % 3 == 0 or n % 100 % 3 == 0:
		ans += 1
		n = 0
	else:
		n = n * 10
print(ans)


import sys

def main():
	s = input()
	n = len(s)
	lim = 243
	ar = [int(c) for c in s]
	dp = [0] * (n + lim + 3)
	for i in range(n - 1, -1, -1):
		x = 0
		k = 1 if ar[i] == 0 else lim
		for j in range(k):
			if i + j == n:
				break
			x = (x * 10 + ar[i + j]) % 3
			dp[i] = max(dp[i], dp[i + j + 1] + (x == 0))
	print(dp[0])
main()


s = input()
n = len(s)
d = [0] * (n + 1)
f = [-1] * 3
r = 0
for i in range(1, n + 1):
	c = int(s[i - 1])
	if c % 3 == 0:
		d[i] = d[i - 1] + 1
	else:
		r = (r + c) % 3
		t = f[r % 3]
		if t > -1 or r == 0:
			d[i] = max(d[t] + 1, d[i - 1])
		else:
			d[i] = d[i - 1]
	f[r % 3] = i
print(d[n])


s = input()
ans = 0
r = 0
r1 = 0
r2 = 0
for i in s:
	n = ord(i) - 48
	if n % 3 == 0:
		ans += 1
		r = r1 = r2 = 0
	else:
		r = r + n % 3
		if r % 3 == 0:
			ans += 1
			r = r1 = r2 = 0
		elif r % 3 == 1:
			if r1 == 1:
				ans += 1
				r = r1 = r2 = 0
			else:
				r1 = 1
		elif r2 == 1:
			ans += 1
			r = r1 = r2 = 0
		else:
			r2 = 1
print(ans)


s = list(map(int, input()))
ans = 0
L = [[]]
for i in s:
	r = i % 3
	if r != 0:
		L[-1].append(r)
	else:
		L.append([])
		ans += 1
n = len(L)
for A in L:
	m = len(A)
	k = 0
	x = 0
	f = [True] * m
	for i in range(m):
		x += A[i]
		if x % 3 == 0 or (i != 0 and A[i - 1] + A[i] == 3 and f[i - 1]):
			x = 0
			f[i] = False
			k += 1
	kk = 0
	ans += max(k, kk)
print(ans)


a = input()
l = len(a)
count = 0
num = ''
for i in range(l):
	b = int(a[i])
	if b == 0:
		count += 1
		num = ''
	elif b % 3 == 0:
		count += 1
		num = ''
	else:
		num += str(b)
		if int(num) % 100 % 3 == 0 or int(num) % 3 == 0:
			count += 1
			num = ''
print(count)


s = list(map(lambda o: int(o), list(input())))
s.reverse()
sm = c = cc = 0
for i in s:
	cc += 1
	sm += i
	if not i % 3 or not sm % 3 or cc == 3:
		c += 1
		sm = 0
		cc = 0
print(c)


s = input()
Visited = [False] * 200010
k = 0
for i in range(len(s)):
	if int(s[i]) % 3 == 0:
		k += 1
		Visited[i] = True
if len(s) >= 2:
	if Visited[0] == False == Visited[1]:
		if (int(s[0]) + int(s[1])) % 3 == 0:
			k += 1
			Visited[0] = True
			Visited[1] = True
for i in range(2, len(s)):
	if Visited[i] == False == Visited[i - 1]:
		if (int(s[i]) + int(s[i - 1])) % 3 == 0:
			k += 1
			Visited[i] = True
			Visited[i - 1] = True
	if Visited[i] == Visited[i - 1] == Visited[i - 2] == False:
		if True:
			k += 1
			Visited[i] = True
			Visited[i - 1] = True
print(k)


s = input()
n = len(s)
r = [0] * n
for i in range(n):
	r[i] = int(s[i]) % 3
i = 0
c = 0
while i < n:
	if i + 2 < n and (r[i] == r[i + 1] == r[i + 2] == 1 or r[i] == r[i + 1] == r[i + 2] == 2):
		c += 1
		i += 3
	elif i + 1 < n and (r[i] == 2 and r[i + 1] == 1 or (r[i] == 1 and r[i + 1] == 2)):
		c += 1
		i += 2
	elif r[i] == 0:
		c += 1
		i += 1
	else:
		i += 1
print(c)


c = 0
f = [0, -1, -1]
z = [0]
for (e, i) in enumerate(input()):
	c = (c + int(i)) % 3
	z.append(z[-1])
	if f[c] != -1:
		z[-1] = max(z[-1], z[f[c]] + 1)
	f[c] = e + 1
print(z[-1])


s = input()
c = 0
i = 0
while i < len(s):
	if int(s[i]) == 0:
		c += 1
		i += 1
	elif int(s[i]) % 3 == 0:
		c += 1
		i += 1
	else:
		c1 = int(s[i])
		pre = int(s[i])
		j = i + 1
		c3 = 0
		while j < len(s):
			if int(s[j]) == 0:
				j += 1
				c3 = 1
				break
			elif int(s[j]) % 3 == 0:
				j += 1
				c3 = 1
				break
			elif (c1 + int(s[j])) % 3 == 0:
				j += 1
				c3 = 1
				break
			else:
				c1 += int(s[j])
				if (c1 - pre) % 3 == 0:
					c3 = 1
					j += 1
					break
				pre = int(s[j - 1])
				j += 1
		if c3 == 1:
			c += 1
		i = j
print(c)


def is_divisible_by_3(num):
	if len(num) > 1 and num[0] == '0':
		return 0
	if sum((int(d) for d in num)) % 3 == 0:
		return 1
	return 0

def main():
	n = input()
	l = len(n)
	dp = [0] * (l + 1)
	dp[0] = 0
	for i in range(1, l + 1):
		for j in range(1, 5):
			index = max(0, i - j)
			dp[i] = max(dp[index] + is_divisible_by_3(n[index:i]), dp[i])
	print(dp[l])
main()


item = str(input())
myn = [[0, -1, -1] for i in range(0, len(item) + 1)]
cindex = 1
for char in item:
	v = int(char) % 3
	if v == 0:
		myn[cindex][0] = max([myn[cindex - 1][1], myn[cindex - 1][2], myn[cindex - 1][0] + 1])
		myn[cindex][1] = myn[cindex - 1][1]
		myn[cindex][2] = myn[cindex - 1][2]
	elif v == 1:
		myn[cindex][0] = max([myn[cindex - 1][2] + 1, myn[cindex - 1][0], myn[cindex - 1][1]])
		myn[cindex][2] = max([myn[cindex - 1][1]])
		myn[cindex][1] = max([myn[cindex - 1][0]])
	elif v == 2:
		myn[cindex][0] = max([myn[cindex - 1][1] + 1, myn[cindex - 1][0], myn[cindex - 1][2]])
		myn[cindex][1] = max([myn[cindex - 1][2]])
		myn[cindex][2] = max([myn[cindex - 1][0]])
	cindex += 1
print(max(myn[-1]))


s = input()
(count, ans, tmp) = (0, 0, 0)
for i in s:
	if int(i) % 3 == 0 or (tmp + int(i)) % 3 == 0 or count == 2:
		tmp = 0
		ans += 1
		count = 0
	else:
		tmp += int(i)
		count += 1
print(ans)


s = input()
rs = [(ord(c) - ord('0')) % 3 for c in s]
res = 0
curRem = 0
curCount = 0
for rem in rs:
	if rem == 0:
		res += 1
		curRem = 0
		curCount = 0
	else:
		curRem += rem
		curCount += 1
		if curRem % 3 == 0 or curCount >= 3:
			res += 1
			curRem = 0
			curCount = 0
print(res)


s = input()
n = len(s)
suma = 0
c = 0
a = []
for i in range(n):
	a.append(int(s[i]) % 3)
	if a[i] == 0:
		c += 1
for i in range(n):
	if a[i] == 1:
		if i < n - 1:
			if a[i + 1] == 2:
				c += 1
				a[i] = 0
				a[i + 1] = 0
				continue
		if i < n - 2:
			if a[i + 1] == 1 and a[i + 2] == 1:
				c += 1
				a[i] = 0
				a[i + 1] = 0
				a[i + 2] = 0
				continue
		continue
	if a[i] == 2:
		if i < n - 1:
			if a[i + 1] == 1:
				c += 1
				a[i] = 0
				a[i + 1] = 0
				continue
		if i < n - 2:
			if a[i + 1] == 2 and a[i + 2] == 2:
				c += 1
				a[i] = 0
				a[i + 1] = 0
				a[i + 2] = 0
				continue
		continue
print(c)


s = input()
s = [int(i) % 3 for i in s]
r = 0
segs = []
curr_seg = []
for i in s:
	if i == 0:
		r += 1
		if curr_seg:
			segs.append(curr_seg)
		curr_seg = []
		continue
	curr_seg.append(i)
if curr_seg:
	segs.append(curr_seg)
new_segs = []
for seg in segs:
	curr_seg = []
	i = 0
	while i < len(seg) - 1:
		if i < len(seg) - 2 and seg[i] == seg[i + 1] == seg[i + 2]:
			r += 1
			i += 3
			if curr_seg:
				new_segs.append(curr_seg)
			curr_seg = []
			continue
		if seg[i] == 1 and seg[i + 1] == 2 or (seg[i] == 2 and seg[i + 1] == 1):
			r += 1
			i += 2
			if curr_seg:
				new_segs.append(curr_seg)
			curr_seg = []
			continue
		curr_seg.append(seg[i])
		i += 1
	if i == len(seg) - 1:
		curr_seg.append(seg[i])
	if curr_seg:
		new_segs.append(curr_seg)
segs = new_segs
for seg in segs:
	r += len(seg) // 3
print(r)


s = input()
dp = [0 for i in range(len(s) + 1)]
f = [0, -1, -1]
pre = 0
for i in range(1, len(s) + 1):
	pre += int(s[i - 1])
	dp[i] = dp[i - 1]
	if f[pre % 3] != -1:
		dp[i] = max(dp[f[pre % 3]] + 1, dp[i - 1])
	f[pre % 3] = i
print(dp[-1])


a = list(map(int, list(input())))
if a[0] % 3 == 0:
	cnt = 1
	last_free = 1
else:
	cnt = 0
	last_free = 0
for i in range(1, len(a)):
	if a[i] % 3 == 0:
		cnt += 1
		last_free = i + 1
	else:
		sm = 0
		for j in range(i, last_free - 1, -1):
			sm += a[j]
			if sm % 3 == 0:
				cnt += 1
				last_free = i + 1
				break
print(cnt)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
from collections import deque
import heapq
import math
import statistics

def sin():
	return input()

def ain():
	return list(map(int, sin().split()))

def sain():
	return input().split()

def iin():
	return int(sin())
MAX = float('inf')
MIN = float('-inf')

def main():
	n = list(map(int, sin()))
	j = 1
	count = 0
	suma = 0
	d = set()
	for i in n:
		if i % 3 == 0:
			count += 1
			suma = 0
			d = set()
		else:
			suma += i
			if suma % 3 == 0:
				count += 1
				suma = 0
				d = set()
			else:
				i = 1
				while 3 * i <= suma:
					if suma - 3 * i in d:
						count += 1
						d = set()
						suma = 0
						break
					i += 1
				d.add(suma)
	print(count)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin, stdout
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
from functools import lru_cache

@lru_cache(None)
def fn(pos, rem):
	if pos < 0:
		return 0
	cur_rem = int(s[pos]) % 3
	ans = fn(pos - 1, 0)
	if (rem + cur_rem) % 3 == 0 or cur_rem == 0:
		ans = max(1 + fn(pos - 1, 0), ans)
	ans = max(ans, fn(pos - 1, (rem + cur_rem) % 3))
	return ans
for _ in range(1):
	s = input()
	n = len(s)
	NI = float('-inf')
	dp = [[NI for i in range(3)] for i in range(n + 1)]
	dp[0][0] = 0
	for i in range(1, n + 1):
		for j in range(3):
			cur_rem = int(s[i - 1]) % 3
			dp[i][j] = dp[i - 1][0]
			if cur_rem == 0 or (j + cur_rem) % 3 == 0:
				dp[i][j] = max(dp[i][j], 1 + dp[i - 1][0])
			dp[i][j] = max(dp[i][j], dp[i - 1][(j + cur_rem) % 3])
	print(dp[n][0])


s = input()
sum = 0
counter = 0
num_now = ''
for i in s:
	if int(num_now + i) % 3 == 0:
		counter += 1
		num_now = ''
		sum = 0
	else:
		num_new = num_now
		norm = False
		while num_new != '':
			num_new = num_new[1:]
			if int(num_new + i) % 3 == 0:
				counter += 1
				num_now = ''
				sum = 0
				norm = True
				break
		if norm:
			continue
		else:
			num_now += i
			sum += int(i)
print(counter)


S = list(str(input()))
count = 0
temp = [0, 0]
for i in range(0, len(S)):
	if int(S[i]) % 3 == 0:
		count += 1
		temp = [0, 0]
	else:
		vap = int(S[i]) % 3
		if vap == 1:
			if temp[1] == 1:
				count += 1
				temp = [0, 0]
			elif temp[0] == 1:
				temp[1] = 1
			else:
				temp[0] = 1
		if vap == 2:
			if temp[0] == 1:
				count += 1
				temp = [0, 0]
			elif temp[1] == 1:
				temp[0] = 1
			else:
				temp[1] = 1
print(count)


s = input()
n = 0
count = 0
se = set()
for i in s:
	if i == 0 or not int(i) % 3:
		count += 1
		n = 0
		se = set()
		continue
	n += int(i)
	if not n % 3:
		count += 1
		n = 0
		se = set()
		continue
	if n - n // 3 * 3 in se:
		count += 1
		se = set()
		n = 0
		continue
	se.add(n % 3)
print(count)


s = ' ' + input()
dp = [0] * len(s)
for i in range(1, len(s)):
	sum = 0
	for j in range(i, 0, -1):
		sum += int(s[j])
		if sum % 3 == 0:
			dp[i] = max(dp[j - 1] + 1, 1)
			break
	dp[i] = max(dp[i], dp[i - 1])
print(dp[-1])


s = input()
y = []
for i in s:
	y.append(int(i))
s = 0
dp = []
count = 0
for i in y:
	if i % 3 != 0:
		j = 0
		dp.append(i)
		while j < len(dp) - 1:
			dp[j] = dp[j] + i
			if dp[j] % 3 == 0:
				dp = []
				count += 1
				break
			j += 1
	else:
		count += 1
		dp = []
print(count)


s = input()
ans = 0
sums = 0
no = 0
for i in s:
	x = int(i)
	sums += x
	no += 1
	if x % 3 == 0 or sums % 3 == 0 or no % 3 == 0:
		ans += 1
		sums = 0
		no = 0
print(ans)


s = input()
i = 0
res = 0
while i < len(s):
	while i < len(s) and s[i] == '0':
		i += 1
		res += 1
	contains = [0, 0, 0]
	j = i
	for j in range(i, len(s)):
		val = int(s[j]) % 3
		contains[val] += 1
		if contains[0] or (contains[1] and contains[2]) or contains[1] == 3 or (contains[2] == 3):
			res += 1
			break
	i = j + 1
print(res)


s = input()
l = []
c = 0
for i in range(len(s)):
	if int(s[i]) % 3 == 0:
		c += 1
		l = []
	else:
		l.append(int(s[i]))
		for j in range(len(l) - 1):
			l[j] += int(s[i])
			if l[j] % 3 == 0:
				c += 1
				l = []
				break
print(c)


str = input()
tmpstr = ''
counter = sum = 0
for num in str:
	if int(num) % 3 == 0:
		counter += 1
		tmpstr = ''
		sum = 0
	else:
		tmpstr += num
		sum += int(num)
		if sum % 3 == 0:
			counter += 1
			tmpstr = ''
			sum = 0
		else:
			for i in range(0, len(tmpstr) - 2):
				sum -= int(tmpstr[i])
				if sum % 3 == 0:
					counter += 1
					tmpstr = ''
					sum = 0
					break
print(counter)


s = input().strip()
ans = []
prefix = 0
s1 = set()
for i in s:
	t = int(i)
	if t % 3 == 0:
		ans.append(0)
		prefix = 0
		s1 = set()
	elif t % 3 == 1 and 2 in s1:
		ans.append(0)
		prefix = 0
		s1 = set()
	elif t % 3 == 2 and 1 in s1:
		ans.append(0)
		prefix = 0
		s1 = set()
	else:
		prefix = (prefix + t) % 3
		ans.append(prefix)
		s1.add(prefix)
print(ans.count(0))


ls = [int(i) % 3 for i in input()]
ls.reverse()
cnt = 0
t = 0
s = 0
for (j, i) in enumerate(ls):
	if i == 0 or t + i == 3 or s + i == 3:
		s = 0
		t = 0
		cnt += 1
	else:
		t = (t + i) % 3
		s = i
print(cnt)


s = input()
s = '#' + s
res = 0
n = len(s)
dp = [0] * n
l = 0
for i in range(1, n):
	j = int(s[i:i + 1])
	if j == 0 or j % 3 == 0:
		dp[i] = dp[i - 1] + 1
		l = i
		continue
	dp[i] = dp[i - 1]
	t = j
	for k in range(i - 1, l, -1):
		t += int(s[k:k + 1])
		if t % 3 == 0:
			dp[i] += 1
			l = i
print(dp[n - 1])


s = input()
r = 0
stack = 0
count = 0
for c in s:
	n = int(c) % 3
	if n == 0 or (n + r) % 3 == 0 or stack == 2:
		count += 1
		r = 0
		stack = 0
	else:
		r += n
		stack += 1
print(count)


from collections import defaultdict, Counter
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
slmii = lambda : sorted(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	s = li()
	n = len(s)
	cnt = 0
	sm = 0
	for i in range(n):
		s[i] = int(s[i]) % 3
	i = 0
	while i < n:
		if s[i] == 0:
			cnt += 1
			sm = 0
			i += 1
		else:
			sm += s[i]
			if sm % 3 == 0:
				sm = 0
				cnt += 1
				i += 1
			elif i + 1 < n and s[i] + s[i + 1] == 3:
				i += 2
				cnt += 1
				sm = 0
			else:
				i += 1
	print(cnt)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


a = str(input())
a = 'x' + a
n = len(a)
f = [0 for i in range(0, 10 ** 6)]
k = 0
for i in range(1, n):
	if int(a[i]) % 3 == 0:
		f[i] = f[i - 1] + 1
		k = i
	else:
		for j in range(i - 1, k, -1):
			if int(a[j:i + 1]) % 3 == 0:
				f[i] = f[k] + 1
				k = i
		else:
			f[i] = f[k]
maxf = 0
for i in range(0, n):
	maxf = max(maxf, f[i])
print(maxf)


S = input()
(n, c) = (0, len(S))
for i in reversed(range(len(S))):
	for k in range(i, c):
		if int(S[i:k + 1]) % 3 == 0:
			n += 1
			c = i
			break
print(n)


import sys
input = lambda : sys.stdin.readline().strip('\r\n')
n = input()
ans = 0
alpha = 0
s = 0
for i in n:
	s += int(i)
	alpha += 1
	if s % 3 == 0 or alpha % 3 == 0 or int(i) % 3 == 0:
		ans += 1
		alpha = 0
		s = 0
print(ans)


s = input()
lis = [0, -1, -1]
sol = [0]
r = 0
for i in range(len(s)):
	r = (r + int(s[i])) % 3
	if lis[r] != -1:
		sol.append(max(sol[-1], 1 + sol[lis[r]]))
	else:
		sol.append(sol[-1])
	lis[r] = i + 1
print(sol[-1])


s = str(input())
prev_sum = 0
ans = 0
f_el = 0
need = True
for el in s:
	el = int(el)
	if el % 3 == 0:
		ans += 1
		prev_sum = 0
		need = True
		continue
	if need:
		f_el = el
		need = False
		prev_sum = el
		continue
	prev_sum += el
	if prev_sum % 3 == 0 or (prev_sum - f_el) % 3 == 0:
		ans += 1
		prev_sum = 0
		need = True
print(ans)


def main():
	a = [int(i) % 3 for i in input()]
	d = []
	k = 0
	ans = 0
	summ = 0
	for i in a:
		if i == 0:
			ans += 1
			k = 0
			summ = 0
			d = []
		else:
			d += [i]
			k += 1
			summ += i
			if k != 1:
				if summ % 3 == 0:
					ans += 1
					summ = 0
					k = 0
					d = []
				elif d[0] == summ % 3:
					ans += 1
					summ = 0
					k = 0
					d = []
	print(ans)
main()


lis = [int(x) % 3 for x in list(input())]
n = len(lis)
dp = []
for i in range(0, n):
	best = (1 if lis[i] == 0 else 0) + (dp[i - 1] if i - 1 >= 0 else 0)
	if i - 1 >= 0:
		best = max(best, (dp[i - 2] if i - 2 >= 0 else 0) + (1 if (lis[i] + lis[i - 1]) % 3 == 0 else 0))
	if i - 2 >= 0:
		best = max(best, (dp[i - 3] if i - 3 >= 0 else 0) + (1 if (lis[i] + lis[i - 1] + lis[i - 2]) % 3 == 0 else 0))
	dp.append(best)
print(dp[n - 1])


li = [int(x) % 3 for x in input()]
start = 0
end = 0
ans = 0
while end < len(li):
	if li[end] == 0:
		ans += 1
		end += 1
		start = end
	else:
		count = 1
		add = li[end]
		while end - count >= start:
			add += li[end - count]
			if add % 3 == 0:
				ans += 1
				start = end + 1
				break
			else:
				count += 1
		end += 1
print(ans)


a = [int(i) for i in list(input())]
current = 0
l = len(a)
for i in range(1, l):
	a[i] += a[i - 1]
a = [0] + a
ans = 0
for i in range(l + 1):
	for j in range(current, i):
		if (a[i] - a[j]) % 3 == 0:
			ans += 1
			current = i
			break
print(ans)


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def Bs(a, x):
	i = 0
	j = 0
	left = 1
	right = x
	flag = False
	while left < right:
		mi = (left + right) // 2
		if a[mi] <= x:
			left = mi + 1
			i += 1
		else:
			right = mi
			j += 1
	if left > 0 and a[left - 1] == x:
		return (i - 1, j)
	else:
		return (-1, -1)

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = I()
	return n

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	if n > 2:
		l.append(n)
	return l
k = 1
for _ in range(k):
	s = list(map(int, input().strip()))
	(o, t) = (0, 0)
	ans = 0
	d = {}
	(d[1], d[2]) = (0, 0)
	for i in range(len(s)):
		if s[i] % 3 == 0:
			ans += 1
			(d[1], d[2]) = (0, 0)
		else:
			d[s[i] % 3] += 1
		if d[1] >= 1 and d[2] >= 1:
			ans += 1
			(d[1], d[2]) = (0, 0)
		if d[1] == 3 or d[2] == 3:
			ans += 1
			(d[1], d[2]) = (0, 0)
	print(ans)


s = input()
n = len(s)
c = [0] * n
r = [0] * n
if s[0] in ['3', '6', '9']:
	c[0] = 1
else:
	c[0] = 0
	r[0] = int(s[0]) % 3
j = 1
while j < n:
	if int(s[j]) % 3 == 0:
		c[j] = c[j - 1] + 1
	elif r[j - 1] == 4:
		r[j] = 0
		c[j] = c[j - 1] + 1
	elif int(s[j]) % 3 == r[j - 1]:
		r[j] = 4
		c[j] = c[j - 1]
	elif int(s[j]) % 3 != r[j - 1] and r[j - 1] != 0:
		r[j] = 0
		c[j] = c[j - 1] + 1
	else:
		r[j] = int(s[j]) % 3
		c[j] = c[j - 1]
	j = j + 1
print(c[-1])


s = input()
l = [0] * 200005
s = '#' + s
for i in range(1, len(s)):
	l[i] = l[i - 1]
	if i == 1:
		if int(s[i]) % 3 == 0:
			l[i] = 1
	elif i == 2:
		if int(s[i]) % 3 == 0:
			l[i] = max(l[i], l[i - 1] + 1)
		if int(s[i - 1:i + 1]) % 3 == 0:
			l[i] = max(l[i], l[i - 2] + 1)
	else:
		if int(s[i]) % 3 == 0:
			l[i] = max(l[i], l[i - 1] + 1)
		if int(s[i - 1:i + 1]) % 3 == 0:
			l[i] = max(l[i], l[i - 2] + 1)
		if int(s[i - 2:i + 1]) % 3 == 0:
			l[i] = max(l[i], l[i - 3] + 1)
print(l[len(s) - 1])


s = input().strip()
have_one = 0
have_two = 0
res = 0
for c in s:
	x = int(c)
	if x % 3 == 1:
		have_one += 1
	elif x % 3 == 2:
		have_two += 1
	else:
		res += 1
		have_one = 0
		have_two = 0
	if have_one == 3 or have_two == 3 or (have_one > 0 and have_two > 0):
		res += 1
		have_one = 0
		have_two = 0
print(res)


s = str(input())
c = 0
cont = 0
su = 0
for i in range(len(s)):
	k = int(s[i]) % 3
	if k == 0:
		c += 1
		su = 0
		cont = 0
	else:
		if k == 1:
			su += 1
		else:
			su += 2
		cont += 1
		if su % 3 == 0 or cont == 3:
			c += 1
			cont = 0
			su = 0
print(c)


s = input()
count = 0
val = 0
ls = [0, 0, 0]
for i in range(len(s)):
	if s[i] == '0':
		count += 1
		val = 0
		ls = [0, 0, 0]
	elif int(s[i]) % 3 == 0:
		count += 1
		val = 0
		ls = [0, 0, 0]
	else:
		val += int(s[i])
		ls[int(s[i]) % 3] += 1
		if val > 0 and val % 3 == 0:
			count += 1
			val = 0
			ls = [0, 0, 0]
		elif ls[1] > 0 and ls[2] > 0:
			count += 1
			val = 0
			ls = [0, 0, 0]
print(count)


l = list(map(int, list(input())))
ans = 0
for i in range(len(l)):
	if l[i] % 3 == 0:
		ans = ans + 1
i = 0
while i < len(l):
	if l[i] % 3 != 0:
		s = 0
		x = set()
		x.add(0)
		while l[i] % 3 != 0:
			s = s + l[i]
			i = i + 1
			if s % 3 in x:
				ans = ans + 1
				break
			else:
				x.add(s % 3)
			if i == len(l):
				break
	else:
		i = i + 1
print(ans)


s = input()
cnt = [0] * 3
ans = 0
sm = 0
for i in s:
	if int(i) % 3 == 0:
		cnt = [0] * 9
		ans += 1
		sm = 0
	elif cnt[(3 - int(i)) % 3] or (sm + int(i)) % 3 == 0:
		cnt = [0] * 3
		ans += 1
		sm = 0
	else:
		cnt[int(i) % 3] += 1
		sm += int(i)
print(ans)


l = [*map(lambda x: int(x) % 3, input())]
dp = [0, -float('inf'), -float('inf')]
for d in l:
	new_dp = [-float('inf')] * 3
	new_dp[d] = max(0, max(dp) + (d == 0))
	new_dp[0] = max(new_dp[0], dp[-d % 3] + 1)
	for r in (1, 2):
		new_dp[r] = max(new_dp[r], dp[(r - d) % 3])
	dp = new_dp
print(max(dp))


import sys, math, itertools, collections, bisect
input = lambda : sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 3
mans = inf
ans = 0
count = 0
pro = 1
A = list(map(int, input()))
n = len(A)
for (i, ai) in enumerate(A):
	A[i] = A[i] % mod
last = now = 0
for (i, ai) in enumerate(A):
	if ai == 0:
		last = now = 0
		ans += 1
	elif (ai + now) % 3 == 0 or (ai + last) % 3 == 0:
		last = now = 0
		ans += 1
	else:
		now += ai
		last = ai
print(ans)


s = list(map(int, input()))
n = len(s)
pre = []
temp = 0
save = [-1 for i in range(3)]
save[0] = 0
for v in s:
	pre.append(temp + v)
	temp += v
dp = [0 for i in range(n + 5)]
for i in range(n):
	rem = pre[i] % 3
	dp[i] = max(dp[i], save[rem] + 1)
	dp[i] = max(dp[i], max(save[(rem + 1) % 3], save[(rem + 2) % 3]))
	save[rem] = max(save[rem], dp[i])
print(dp[n - 1])


s = input()
(total, count, tmp) = (0, 0, 0)
for i in range(len(s)):
	if int(s[i]) % 3 == 0 or (tmp + int(s[i])) % 3 == 0 or count == 2:
		total += 1
		tmp = 0
		count = 0
	else:
		count += 1
		tmp = int(s[i])
print(total)


import sys
from math import *

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

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())
s = list(minp())
n = len(s)
b = [-1000] * 3
c = 0
b[0] = 0
for i in range(n):
	c = (c + int(s[i])) % 3
	z = 0
	for j in range(3):
		z = max(z, b[j] + (1 if j == c else 0))
	b[c] = max(b[c], z)
print(b[c])


n = input()
buf = 0
c = 0
m = 0
for i in range(len(n)):
	buf += int(n[i])
	m += 1
	if int(n[i]) % 3 == 0 or buf % 3 == 0 or m >= 3:
		buf = 0
		c += 1
		m = 0
print(c)


s = input()
h = 0
j = 0
ans = 0
for i in s:
	h += int(i)
	j += 1
	if int(i) % 3 == 0 or h % 3 == 0 or j == 3:
		ans += 1
		h = 0
		j = 0
print(ans)


a = input()
su = 0
ans = 0
b = ''
for i in range(len(a)):
	if int(a[i]) % 3 == 0:
		ans += 1
		b += '9'
	else:
		b += str(int(a[i]) % 3)
for i in range(len(b) - 2):
	if int(b[i]) + int(b[i + 1]) == 3:
		ans += 1
		b = b[:i] + '99' + b[i + 2:]
	if int(b[i]) + int(b[i + 1]) + int(b[i + 2]) == 3 or int(b[i]) + int(b[i + 1]) + int(b[i + 2]) == 6:
		ans += 1
		b = b[:i] + '999' + b[i + 3:]
if len(a) >= 2 and int(b[-1]) + int(b[-2]) == 3:
	ans += 1
print(ans)


s = input()
ans = 0
temp = ''
for i in s:
	if int(i) == 0:
		ans += 1
		temp = ''
	else:
		temp += i
		k = int(temp)
		if k % 3 == 0:
			ans += 1
			temp = ''
		else:
			su = 0
			for j in temp:
				su += int(j)
			for j in temp:
				su -= int(j)
				if su % 3 == 0 and su != 0:
					ans += 1
					temp = ''
print(ans)


from __future__ import division, print_function
from sys import stdin, stdout
import bisect
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
from collections import Counter
import collections
import math
import heapq
import re

def modinv(n, p):
	return pow(n, p - 2, p)

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())

def Divisors(n):
	l = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n // i == i:
				l.append(i)
			else:
				l.append(i)
				l.append(n // i)
	return l

def most_frequent(list):
	return max(set(list), key=list.count)

def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def ncr(n, r, p):
	t = fact[n] * (ifact[r] * ifact[n - r] % p) % p
	return t

def Convert(string):
	li = list(string.split(''))
	return li

def SieveOfEratosthenes(n):
	global prime
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	f = []
	for p in range(2, n):
		if prime[p]:
			f.append(p)
	return f
prime = []
q = []

def dfs(n, d, v, c):
	global q
	v[n] = 1
	x = d[n]
	q.append(n)
	j = c
	for i in x:
		if i not in v:
			f = dfs(i, d, v, c + 1)
			j = max(j, f)
	return j

def main():
	a = list(map(int, str(input())))
	count = 0
	s = 0
	ans = 0
	temp = []
	for i in range(len(a)):
		if a[i] % 3 == 0:
			ans += 1
			s = 0
			count = 0
		else:
			if a[i] % 3 == 1:
				s += 1
			else:
				s += 2
			count += 1
			if s % 3 == 0 or count == 3:
				count = 0
				s = 0
				ans += 1
	print(ans)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(s, k, i) = (''.join([str(int(i) % 3) for i in input()]) + '  ', 0, 0)
while i < len(s):
	if s[i] == '0':
		k += 1
		i += 1
	elif s[i:i + 2] in '12.21':
		k += 1
		i += 2
	elif s[i:i + 3] in '111.222':
		k += 1
		i += 3
	else:
		i += 1
print(k)


s = str(input())
i = 0
ans = 0
t = []
while i < len(s):
	if int(s[i]) % 3 == 0:
		ans += 1
		t = []
	else:
		t.append(int(s[i]) % 3)
		if t == [1, 1, 1] or t == [1, 1, 2] or t == [1, 2] or (t == [2, 1]) or (t == [2, 2, 1]) or (t == [2, 2, 2]):
			t = []
			ans += 1
	i = i + 1
print(ans)


s = input()
n = len(s)
(c, r, ans) = (0, 0, 0)
for i in range(n):
	r += int(s[i])
	c += 1
	if int(s[i]) % 3 == 0 or r % 3 == 0 or c == 3:
		ans += 1
		(r, c) = (0, 0)
print(ans)


s = input()
k = 0
ans = 0
vis = {0}
for (i, c) in enumerate(s):
	k += int(c)
	k %= 3
	if k in vis:
		ans += 1
		k = 0
		vis = {0}
	else:
		vis.add(k)
print(ans)


n = input()
ans = 0
b = len(n)
for i in reversed(range(len(n))):
	for k in range(i, b):
		if int(n[i:k + 1]) % 3 == 0:
			ans += 1
			b = i
			break
print(ans)


number = input()
div_3 = 0
number_sum = 0
curr_length = 0
for unit in number:
	number_sum += int(unit)
	curr_length += 1
	if number_sum % 3 == 0 or curr_length >= 3 or int(unit) % 3 == 0:
		div_3 += 1
		(number_sum, curr_length) = (0, 0)
print(div_3)


s = list(map(int, input()))
a = []
l = 0
for i in range(len(s)):
	a.append(s[i] % 3)
	k = 0
	for j in range(len(a) - 1, -1, -1):
		k += a[j]
		if k % 3 == 0:
			l += 1
			a.clear()
			break
print(l)


n = input()
arr = [int(i) for i in n]
sum = 0
temp = []
cnt = 0
for i in arr:
	if i % 3 == 0:
		cnt += 1
		temp = []
	else:
		t = []
		for j in temp:
			t.append(i + j)
		temp += t
		for j in temp:
			if j % 3 == 0:
				cnt += 1
				temp = []
				break
		else:
			temp.append(i)
print(cnt)


line = input()
nums = [int(x) for x in line]
res = 0
has_1 = False
has_2 = False
for num in nums:
	modulo = num % 3
	if modulo == 0:
		res += 1
		has_1 = False
		has_2 = False
	elif has_1 and modulo == 2 or (has_2 and modulo == 1):
		res += 1
		has_1 = False
		has_2 = False
	else:
		if has_1 and modulo == 1:
			has_1 = False
			has_2 = True
		elif has_2 and modulo == 2:
			has_1 = True
			has_2 = False
		if modulo == 1:
			has_1 = True
		else:
			has_2 = True
print(res)


s = input()
like = [len(s), -1, -1]
dp = [0] * (len(s) + 2)
i = len(s) - 1
r = 0
while i >= 0:
	dp[i] = dp[i + 1]
	r = (r + ord(s[i])) % 3
	if like[r] != -1:
		dp[i] = max(dp[i], dp[like[r]] + 1)
	like[r] = i
	i -= 1
print(dp[0])


n = input()
ls = ''
t = 0
for i in range(len(n)):
	if int(n[i]) % 3 == 0:
		ls = ''
		t += 1
	else:
		ls += n[i]
		for j in range(0, len(ls)):
			if int(ls[j:]) % 3 == 0:
				t += 1
				ls = ''
				break
print(t)


s = input()
r = []
for i in range(len(s)):
	r.append(int(s[i]) % 3)
otv = 0
i = 0
n = len(s)
while i < n:
	if r[i] == 0:
		otv += 1
	elif r[i] == 1:
		if i + 1 < n and r[i + 1] == 2:
			otv += 1
			i += 1
		elif i + 1 < n and r[i + 1] == 1 and (i + 2 < n) and (r[i + 2] == 1):
			otv += 1
			i += 2
	elif r[i] == 2:
		if i + 1 < n and r[i + 1] == 1:
			otv += 1
			i += 1
		elif i + 1 < n and r[i + 1] == 2 and (i + 2 < n) and (r[i + 2] == 2):
			otv += 1
			i += 2
	i += 1
print(otv)


lst = map(int, input())
(res, prev, length) = (0, [], 0)
for (i, x) in enumerate(lst):
	if x % 3 == 0:
		res += 1
		(prev, length) = ([], 0)
	else:
		(k, item) = (0, x % 3)
		for j in range(length - 1, -1, -1):
			item = (item + prev[j]) % 3
			if item == 0:
				(res, k, prev, length) = (res + 1, 1, [], 0)
				break
		if k == 0:
			prev.append(x % 3)
			length += 1
print(res)


l = list(input())
s = 0
i = 0
while i + 2 < len(l):
	if int(l[i]) % 3 == 0:
		s += 1
		i += 1
	elif int(l[i]) % 3 == 1:
		if int(l[i + 1]) % 3 == 0:
			s += 1
			i += 2
		elif int(l[i + 1]) % 3 == 1:
			s += 1
			i += 3
		elif int(l[i + 1]) % 3 == 2:
			s += 1
			i += 2
	elif int(l[i]) % 3 == 2:
		if int(l[i + 1]) % 3 == 0:
			s += 1
			i += 2
		elif int(l[i + 1]) % 3 == 1:
			s += 1
			i += 2
		elif int(l[i + 1]) % 3 == 2:
			s += 1
			i += 3
if i == len(l) - 1:
	if int(l[i]) % 3 == 0:
		print(s + 1)
	else:
		print(s)
elif i == len(l) - 2:
	if int(l[i]) % 3 == 0 and int(l[i + 1]) % 3 == 0:
		print(s + 2)
	elif int(l[i]) % 3 == 0 and int(l[i + 1]) % 3 != 0 or (int(l[i]) % 3 != 0 and int(l[i + 1]) % 3 == 0):
		print(s + 1)
	elif int(l[i]) % 3 == 1 and int(l[i + 1]) % 3 == 2 or (int(l[i]) % 3 == 2 and int(l[i + 1]) % 3 == 1):
		print(s + 1)
	else:
		print(s)
else:
	print(s)


import sys

def main():
	s = sys.stdin.readline().strip()
	N = len(s)
	dp = [0] * N
	dp[0] = 1 if int(s[0]) % 3 == 0 else 0
	if len(s) == 1:
		print(dp[0])
		return
	dp[1] = dp[0]
	if int(s[1]) % 3 == 0:
		dp[1] = dp[0] + 1
	if (int(s[1]) + int(s[0])) % 3 == 0:
		dp[1] = max(dp[1], 1)
	if len(s) == 2:
		print(dp[1])
		return
	dp[2] = dp[1]
	if int(s[2]) % 3 == 0:
		dp[2] = 1 + dp[1]
	if (int(s[2]) + int(s[1])) % 3 == 0:
		dp[2] = max(dp[2], dp[0] + 1)
	if (int(s[2]) + int(s[1]) + int(s[0])) % 3 == 0:
		dp[2] = max(dp[2], 1)
	for i in range(3, N):
		ith = int(s[i])
		prev = int(s[i - 1])
		prever = int(s[i - 2])
		dp[i] = dp[i - 1]
		if ith % 3 == 0:
			dp[i] = dp[i - 1] + 1
		if (prev + ith) % 3 == 0:
			dp[i] = max(dp[i], dp[i - 2] + 1)
		if (prever + prev + ith) % 3 == 0:
			dp[i] = max(dp[i], dp[i - 3] + 1)
	print(dp[N - 1])
main()


s = input()
md = [-1, -1, -1]
ac = 0
ans = 0
for i in range(len(s)):
	ac = (ac + int(s[i])) % 3
	if md[ac] != -1 or ac % 3 == 0:
		ans += 1
		ac = 0
		md = [-1 for i in range(3)]
	md[ac] = i
print(ans)


A = list(input())
for i in range(len(A)):
	A[i] = int(A[i])
B = [0] * len(A)
if A[0] % 3 == 0:
	B[0] = 1
for i in range(1, len(A)):
	if A[i] % 3 == 0:
		B[i] = 1
	else:
		sum1 = A[i]
		j = i - 1
		while B[j] != 1 and j >= 0:
			sum1 += A[j]
			if sum1 % 3 == 0:
				B[i] = 1
				break
			j -= 1
		sum1 = 0
print(B.count(1))


s = input()
f = [0] * len(s)
cnt = 0
for i in range(len(s)):
	a = int(s[i])
	if a % 3 == 0:
		cnt += 1
		f[i] = 1
for i in range(len(s) - 1):
	if f[i] == 0 and f[i + 1] == 0:
		a = int(s[i]) * 10 + int(s[i + 1])
		if a % 3 == 0:
			cnt += 1
			f[i] = f[i + 1] = 1
		elif i < len(s) - 2 and f[i] == 0 and (f[i + 1] == 0) and (f[i + 2] == 0):
			a = int(s[i]) * 100 + int(s[i + 1]) * 10 + int(s[i + 2])
			if a % 3 == 0:
				cnt += 1
				f[i] = f[i + 1] = f[i + 2] = 1
for i in range(len(s) - 2):
	if f[i] == 0 and f[i + 1] == 0 and (f[i + 2] == 0):
		a = int(s[i]) * 100 + int(s[i + 1]) * 10 + int(s[i + 2])
		if a % 3 == 0:
			cnt += 1
			f[i] = f[i + 1] = f[i + 2] = 1
for i in range(len(s) - 3):
	if f[i] == 0 and f[i + 1] == 0 and (f[i + 2] == 0) and (f[i + 3] == 0):
		a = int(s[i]) * 1000 + int(s[i + 1]) * 100 + int(s[i + 2]) * 10 + int(s[i + 3])
		if a % 3 == 0:
			cnt += 1
print(cnt)


import sys
sys.setrecursionlimit(10000)
t = 1
for _ in range(t):
	s = input()
	no = ''
	count = 0
	for i in s:
		if int(i) % 3 == 0:
			count += 1
			no = ''
		else:
			no += i
			if int(no) % 3 == 0:
				count += 1
				no = ''
			elif int(no[-2:]) % 3 == 0:
				count += 1
				no = ''
	print(count)


s = input().strip()
d = {}
ss = 0
ans = 0
d[0] = 1
for i in s:
	x = int(i)
	ss += x
	ss %= 3
	if ss in d:
		ss = 0
		d = {}
		ans += 1
	d[ss] = 1
print(ans)


a = list(map(int, input()))
n = len(a)
temp = 0
l = 0
cut = 0
for i in range(n):
	temp = temp + a[i]
	if temp % 3 == 0:
		cut = cut + 1
		temp = 0
		l = i
	elif a[i] % 3 == 0:
		temp = 0
		l = i
		cut = cut + 1
	else:
		temp2 = 0
		for j in range(i, l, -1):
			temp2 = temp2 + a[j]
			if temp2 % 3 == 0:
				cut = cut + 1
				temp = 0
				l = i
				break
print(cut)


s = input()
n = len(s)
ss = 0
f = [1] * n
rem = []
for i in range(n):
	rem.append(int(s[i]) % 3)
ans = rem.count(0)
i = 0
while i < n:
	if rem[i] == 1:
		if i + 1 < n and rem[i + 1] == 2:
			ans += 1
			i += 2
		elif i + 1 < n and rem[i + 1] == 1 and (i + 2 < n) and (rem[i + 2] == 1):
			ans += 1
			i += 3
		else:
			i += 1
	elif rem[i] == 2:
		if i + 1 < n and rem[i + 1] == 1:
			ans += 1
			i += 2
		elif i + 1 < n and rem[i + 1] == 2 and (i + 2 < n) and (rem[i + 2] == 2):
			ans += 1
			i += 3
		else:
			i += 1
	else:
		i += 1
print(ans)


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

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

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

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		s = Sn()
		n = len(s)
		(r, fr) = (0, [0, -1, -1])
		z = [0]
		for i in range(1, n + 1):
			r = (r + int(s[i - 1])) % 3
			z.append(z[i - 1])
			if fr[r] != -1:
				z[i] = max(z[i], z[fr[r]] + 1)
			fr[r] = i
		print(z[-1])
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


s = [int(i) for i in input()]
count = 0
current = []
for (h, i) in enumerate(s):
	for j in range(len(current)):
		current[j] = current[j] * 10 + i
	current.append(i)
	if h + 1 < len(s) and s[h + 1] != 0:
		for m in current:
			if m % 3 == 0:
				count += 1
				current = []
				break
	else:
		for m in current:
			if m % 3 == 0:
				count += 1
				current = []
				break
print(count)


s = input()
p = 0
n = 0
for i in s:
	n += int(i)
	if not n % 3 or not int(i) % 3 or (not n % 100 % 3):
		(p, n) = (p + 1, 0)
	else:
		n *= 10
print(p)


n = input()
cnt = 0
prev = ''
for i in range(len(n)):
	if int(n[i]) % 3 == 0:
		cnt += 1
		prev = ''
	else:
		prev = prev + n[i]
		for i in range(len(prev)):
			b = prev[i:]
			sm = int(b)
			if sm % 3 == 0:
				cnt += 1
				prev = ''
				break
print(cnt)