Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import fractions
from functools import reduce
import copy

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
  
n = int(input())
A = list(int(i) for i in (input().split()))

ans = 0
tmp = 0
reduce_num = 0
for i in range(n):
  if( i != 0): A.append(reduce_num)
  reduce_num = A.pop(0)
  tmp = gcd_list(A)
  if(ans < tmp):
    ans = tmp

print(ans)

### FIXED CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
  
n = int(input())
A = list(int(i) for i in (input().split()))

front = []
end = []
for i in range(n):
  if(i == 0):
    front.append(gcd(*[A[0]]))
    end.append(gcd(*[A[n-1]]))
  else:
    front.append(gcd(*[front[i - 1],A[i]]))
    end.append(gcd(*[end[i - 1],A[n-1-i]]))

ans = 0
for i in range(n):
  if(i == 0):
    tmp = end[n-2]
  elif(i == n-1):
    tmp = front[n-2]
  else:
    tmp = gcd(*[front[i-1],end[n-2-i]])
  if(ans < tmp):
    ans = tmp
print(ans)
### BUGGY CODE ###

N,W=map(int,input().split())
oj=[]
for i in range(N):
  oj.append(list(map(int,input().split())))
M=100*1001
dp=[10**10]*M
dp[0]=0
for i in range(N):
  for j in range(M,-1,-1):
    if j+oj[i][1]<M:
      k=j+oj[i][1]
      dp[k]=min(dp[k],dp[j]+oj[i][0])
v=0
for i in range(M):
  if dp[i]<=W:v=i
print(v)


### FIXED CODE ###

N,W = map(int, input().strip().split(" "))
oj = []
for i in range(N):
    tmp = list(map(int, input().strip().split(" ")))
    oj.append(tmp)

#dp = [0] * (W+1)
M = 100 * 1001
dp = [10**10] * M

dp[oj[0][1]] = oj[0][0]

for i in range(1,N):
    for j in range(M, -1, -1):
        if j + oj[i][1] < M:
            dp[j + oj[i][1]] = min(dp[j + oj[i][1]], dp[j] + oj[i][0])
    dp[oj[i][1]] = min(dp[oj[i][1]], oj[i][0])

v = 0
for i in range(M):
    if dp[i] <= W:
        v = i
print(v)
### BUGGY CODE ###

def tasu(x):
    return x / 2 * (x + 1)

def kitaiti(n , k , p):

    ans = 0
    count = 0
    kitai = [0]*n
    mod = 10**9+7

    for i in range(n):
        kitai[i] = tasu(p[i]) / p[i]

    for i in range(n - k + 1):

        count = sum(kitai[i:i+k]) % mod
 #       for w in range(i , i + k):
#            count += kitai[w]
#            count += tasu(p[w]) / p[w]
        ans = max(ans , count)

    return ans

def main():
    n , k = map(int , input().split())
    p = list(map(int,input().split()))
    print(kitaiti(n , k , p))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def tasu(x):
    return x / 2 * (x + 1)

def kitaiti(n , k , p):

    ans = 0
    count = 0
    kitai = [0]*n
    kitaisum = [0]*n
    mod = 10**9+7

    for i in range(n):
        kitai[i] = tasu(p[i]) / p[i]

    for i in range(n):
        if i == 0:
            kitaisum[i] += kitai[i]
        else:
            kitaisum[i] += kitai[i] + kitaisum[i-1]

    for i in range(n - k + 1):

        ans = max(ans , (kitaisum[i + k - 1] - kitaisum[i-1]) if i != 0 else kitaisum[i + k - 1])

    return ans

def main():
    n , k = map(int , input().split())
    p = list(map(int,input().split()))
    print(kitaiti(n , k , p))

if __name__ == '__main__':
    main()
### BUGGY CODE ###

# C - IDC
import bisect
import sys
readline = sys.stdin.readline

base = 1000000000000
N, M = map(int, readline().split())
P = [0] * M
Y = [0] * M
T = [[] for _ in range(N+1)]

for i in range(M):
    P[i], Y[i] = map(int, readline().split())
    T[P[i]].append(Y[i])
    T[P[i]].sort()

for i in range(M):
    num = bisect.bisect_right(T[P[i]], Y[i])
    print(str(base + P[i]*1000000 + num)[1:])

### FIXED CODE ###

# C - IDC

import bisect
import sys
readline = sys.stdin.readline

base = 1000000000000
N, M = map(int, readline().split())
PY = []
T = [[] for _ in range(N+1)]

for i in range(M):
    P, Y = map(int, readline().split())
    PY.append((P, Y))

PY_sorted = sorted(PY, key=lambda x: x[1])
PY_sorted = sorted(PY_sorted, key=lambda x: x[0])

for i in range(M):
    T[PY_sorted[i][0]].append(PY_sorted[i][1])

for i in range(M):
    n = bisect.bisect_right(T[PY[i][0]], PY[i][1])
    print(str(base + PY[i][0]*1000000 + n)[1:])
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            elif count_list[i - 1][j] >= count_list[i][j - 1]:
                count_list[i][j] = count_list[i - 1][j]
            else:
                count_list[i][j] = count_list[i][j - 1]

    return count_list[m][n]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = list(map(lambda x: x.strip(), _input[1:]))
    # assert len(word_list) == 2 * pair_num
    for k in range(0, len(word_list), 2):
        print(lcs(word_list[k], word_list[k + 1]))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            elif count_list[i - 1][j] >= count_list[i][j - 1]:
                count_list[i][j] = count_list[i - 1][j]
            else:
                count_list[i][j] = count_list[i][j - 1]

    return count_list[m][n]


def lcs_better(A, B):
    costs = [0]
    for c in B:
        for index in range(len(costs) - 1, -1, -1):
            # print(costs, index + 1)
            x_findex_index = A.find(c, costs[index])
            if x_findex_index != -1:
                if index + 1 < len(costs):
                    costs[index + 1] = min(costs[index + 1], x_findex_index + 1)
                else:
                    costs.append(x_findex_index + 1)
    return len(costs) - 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    for k in range(0, len(word_list), 2):
        print(lcs_better(word_list[k].strip(), word_list[k + 1].strip()))
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
R=n//r
ans=0
for i in range(R+1):
  for j in range(((n-i*r)//g)+2):
    if 0<=n-i*r-j*g and (n-i*r-j*g)%b==0:
      ans+=1
print(ans)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
R=n//r
ans=0
for i in range(R+1):
  for j in range(((n-i*r)//g)+2):
    if 0<=n-i*r-j*g and (n-i*r-j*g)%b==0:
      ans+=1
print(ans)
### BUGGY CODE ###

H, W = tuple(map(int, input().split(' ')))

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

def get_arounds(x, y, max_x, max_y):
    arounds = [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]
    return list(filter(lambda a: a[0] >= 0 and a[0] < max_x and
                                 a[1] >= 0 and a[1] < max_y, arounds))

def find_path(point, path, ignore, H, W):
    x = point[0]
    y = point[1]
    arounds = get_arounds(x, y, H, W)
    targets = list(filter(lambda x: not x in ignore, arounds))

    if len(targets) == 0:
        return [(False, path, ignore)]
    else:
        return [(True, path + [target], ignore + arounds)
                for target in targets]


ignore = []
for i in range(0, H):
    for j in range(0, W):
        if not grid[i][j]:
            ignore.append((i, j))

paths = [(True, [(0, 0)], ignore)]
s_path = []
while any([p[0] for p in paths]):
    next_paths = []
    for p in filter(lambda p: p[0], paths):
        if p[1][-1] == (H - 1, W - 1):
            s_path = p[1]
            break

        next_paths.extend(find_path(p[1][-1], p[1], p[2], H, W))
    paths = next_paths

if len(s_path) == 0:
    print(-1)
else:
    print(H * W - len(s_path) - len(ignore))


### FIXED CODE ###

from collections import deque


def get_arounds(point, grid, max_x, max_y):
    x = point[0]
    y = point[1]
    arounds = [(x + dx, y + dy) for dx, dy in ((0, -1), (1, 0), (0, 1), (-1, 0))]
    return list(filter(lambda a: 0 <= a[0] < max_x and
                                 0 <= a[1] < max_y and
                                 grid[a[0]][a[1]], arounds))


H, W = tuple(map(int, input().split()))

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

black = sum(map(lambda l: l.count(False), grid))

grid[0][0] = False
p_grid = {(0, 0): 0}
queue = deque([(0, 0)])
while not len(queue) == 0:
    here = queue.popleft()
    if here == (H - 1, W - 1):
        break;
    arounds = get_arounds(here, grid, H, W)
    for a in arounds:
        grid[a[0]][a[1]] = False
        p_grid[a] = p_grid[here] + 1
    if not arounds:
        continue
    queue.extend(arounds)

if (H-1, W-1) in p_grid:
    print(H * W - (p_grid[H-1, W-1] + 1) - black)
else:
    print(-1)
### BUGGY CODE ###

S = str(input())
h = [int(x) for x in list(S)]
N = len(h)
c = 0
for i in range(0, N+1):
    for j in range(i, N+1):
        b = 0
        for k in range(i, j):
            b = b * 10 + h[k]
        if b != 0 and b % 2019 == 0:
            c += 1
print(c)

### FIXED CODE ###

S = input()
P = 2019
N = len(S)
num = [0] * P
num[0] = 1
c = 0
ans = 0
dgt = 1
for i in range(N-1, -1, -1):
    c = (c + int(S[i]) * dgt) % P
    dgt *= 10
    dgt %= P
    ans += num[c]
    num[c] += 1

print(ans)
### BUGGY CODE ###

x=int(input())
n=10**5
import math
def eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q=eratosthenes(n)

ans=[0]*(10**5+1)
for i in range(10**5):
    ans[i+1]=ans[i]+(1 if i+1 in q and (i+1+1)//2 in q else 0 )
for i in range(x):
    l,r = map(int,input().split())	
    print(ans[r]-ans[l-1])

### FIXED CODE ###

x=int(input())
n=10**5
import math
def eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q=eratosthenes(n)

ans=[0]*(10**5+1)
for i in range(10**5):
    ans[i+1]=ans[i]+(1 if i+1 in q and (i+1+1)//2 in q else 0 )
for i in range(x):
    l,r = map(int,input().split())	
    print(ans[r]-ans[l-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = list(map(int, readline().split()))
Q = int(readline())

for line in readlines():
    B, C = map(int, line.split())

    A = [(C if num == B else num) for num in A]
    print(sum(A))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter
readline = sys.stdin.buffer.readline

N = int(readline())
A = list(map(int, readline().split()))
Q = int(readline())
d = Counter(A)

total = sum(A)

for _ in range(Q):
    B, C = map(int, readline().split())

    total -= B * d[B]
    total += C * d[B]

    d[C] += d[B]
    d[B] = 0

    print(total)
### BUGGY CODE ###

def cmd(l,command):
    if command == 'deleteFirst':
        if len(l)>0:
            l.pop(0)
    elif command == 'deleteLast':
        if len(l)>0:
            l.pop(-1)
    else:
        ope, num = command.split()
        num = int(num)
        if ope == 'insert':
            l.insert(0,num)
        else:
            if num in l:
                l.remove(num)


if __name__ == '__main__' :
    l = list()
    n = input()
    for i in range(n):
        cmd(l,raw_input())

    for i in range(len(l)-1):
        print l[i],
    print l[-1]

### FIXED CODE ###

from collections import deque

class MyList(deque):
    def __init__(self):
        self.__init__ = deque
        self.d = {'deleteFirst':self.delF, 'deleteLast':self.delL, 'insert':self.insX, 'delete':self.delX}
    def cmd(self,command):
        if ' ' in command:
            ope, num = command.split()
            num = int(num)
            self.d[ope](num)
        else:
            self.d[command]()
            
    def delF(self):
        self.popleft()

    def delL(self):
        self.pop()

    def insX(self,num):
        self.appendleft(num)

    def delX(self,num):
        if num in self:
            self.remove(num)

if __name__ == '__main__' :
    l = MyList()
    n = input()
    
    for i in range(n):
        l.cmd(raw_input())

    q = deque(l)
    for i in range(len(l)-1):
        print q.popleft(),
    print l[-1]
### BUGGY CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))

m = prev = sum(P[:k])
s = 0
for i in range(1, n - k + 1):
    tmp = prev - P[i - 1]+ P[i + k - 1]
    prev = tmp
    if tmp > m:
        s = i
    m = max(tmp, m)

ans = 0
for i in range(s, s + k):
    p = P[i]
    ans += sum(range(p + 1)) / p
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))

m = prev = sum(P[:k])
s = 0
for i in range(1, n - k + 1):
    tmp = prev - P[i - 1]+ P[i + k - 1]
    prev = tmp
    if tmp > m:
        s = i
    m = max(tmp, m)

ans = 0
d = dict()
for i in range(s, s + k):
    p = P[i]
    if p not in d.keys():
        tmp = sum(range(p + 1)) / p
        ans += tmp
        d[p] = tmp
    else:
        ans += d[p]
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
a = [input() for i in range(N)]
li = []
count = 0
for i in a:
    li.append(collections.Counter(i))
for i in range(N):
    for k in range(1+i,N):
        if li[i] == li[k]:
            count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = [''.join(sorted(input().rstrip())) for _ in range(N)]


from collections import Counter
counter = Counter(S)
answer = sum(x * (x - 1) // 2 for x in counter.values())
print(answer)
### BUGGY CODE ###

n = int(input())
s = str(input())
L =[]
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            L.append(s[i]+s[j]+s[k])
print(len(set(L)))


### FIXED CODE ###

n = int(input())
s = str(input())
cnt = 0
for i in range(1000):
    x = str(i).zfill(3)
    i1 = s.find(x[0])
    i2 = s[i1+1:].find(x[1])
    i3 = s[i1+i2+2:].find(x[2])
    if -1 not in (i1, i2, i3):
        cnt += 1
print(cnt)
### BUGGY CODE ###

import itertools
def comb(lis, k):
    l_sum = [sum(pair) for pair in itertools.combinations(lis, k)]
    return len(set(l_sum))
    
n, k = map(int, input().split())
ans = 0
l = [i for i in range(n+1)]
for i in range(k, n+2):
    ans += comb(l, i)
    
mod = 10 ** 9 + 7
print(ans % mod)

### FIXED CODE ###

n, k = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7

n_min = sum([i for i in range(0, k-1)])
n_max = sum([n - i for i in range(0, k-1)])

for i in range(k-1, n+1):
  n_min += i
  n_max += n - i
  ans += n_max - n_min + 1
    
print(ans % mod)
### BUGGY CODE ###

N = int(input())
S =[]
for n in range(N):
    s = input()
    S.append(s[0])
S=sorted(S)
NAME = sorted(["M","A","R","C","H"])
from itertools import combinations
pattern = list(combinations(NAME,3))
LEN = len(S)
cnt=0
for s1 in range(LEN-2):
    for s2 in range(s1+1,LEN-1):
        for s3 in range(s2+1,LEN):
            if (S[s1],S[s2],S[s3]) in pattern:
                cnt+=1
print(cnt)

### FIXED CODE ###

N = int(input())
S =[]
for n in range(N):
    s = input()
    S.append(s[0])
S=sorted(S)
NAME = sorted(["M","A","R","C","H"])
from itertools import combinations
from collections import Counter
pattern = list(combinations(NAME,3))
LEN = len(S)
cnt=0
Counter_S =Counter(S)
cnt = 0
for p in pattern:
    cnt +=(Counter_S[p[0]] * Counter_S[p[1]] * Counter_S[p[2]])
print(cnt)
### BUGGY CODE ###

#!/use/bin/env python3

a = input()

ans = sum(range(1, int(a)))

print(ans)

### FIXED CODE ###

#!/use/bin/env python3

a = input()

b = int(a)

ans = 0

if b != 2:
    if b % 2 == 1:
        ans = b * ((b - 1) // 2)
    else:
        ans = b * ((b - 1) // 2) + (b // 2)
else:
    ans = 1

print(ans)
### BUGGY CODE ###

import collections

def main():
    n = int(input())
    s = [[] for i in range(n)]
    count = 0

    for i in range(n):
        s[i] = input()

    for num,i in enumerate(s):
        s[num] = collections.Counter(i)

    for i in range(n):
        for j in range(i+1,n):
            if s[i] == s[j]:
                count = count + 1

    print(count)


if __name__ == '__main__' :
    main()

### FIXED CODE ###

from collections import Counter

n = int(input())
count = 0
lists =[]
count_dict = Counter()

for i in range(n):
    input_data = ''.join(sorted(input()))
    if input_data in count_dict:
        count += count_dict[input_data]
        count_dict[input_data] += 1
    else:
        count_dict[input_data] = 1

print(count)
### BUGGY CODE ###

from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1], reverse=True)

    for s in S:
        b = s[0]
        c = s[1]
        if c >= cards[-1]:
            cards = cards[b:] + [c for _ in range(b)]
            #print(cards)
            continue
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        else:
            break
    return sum(cards)

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import collections

    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    grid = [[item for item in input()] for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                    que.appendleft([ny, nx, w_num])
                    fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                nw = w_num +1
                if grid[ny][nx] == '.' and fp[ny][nx] > nw:
                    que.append([ny, nx, nw])
                    fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

def main():
    si = int(input())
    s = list(str(si))
    if '0' in s:
        print(0)
        return
    

    sm = []
    for i, ss in enumerate(s):
        ssi = int(ss)
        if i == 0:
            sm.append(ssi)
        else:
            sm.append(ssi + sm[-1])
    ans = 0
    for i in range(len(s)):
        if i == 0:
            tmp = 0
        else:
            tmp = sm[i-1]

        for j in range(i+1,len(s)):

            if (sm[j] - tmp) % 3 != 0:
                continue
            a = ''
            for k, aa in enumerate(s[i:j+1]):
                a += aa
            if int(a) % 673 == 0:
                ans += 1

    print(ans)
    # print(sm)
if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)


S = input()
N = len(S)
P = 2019

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    sys.exit()

num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

print(ans)
### BUGGY CODE ###

import collections
N=int(input())
s=[str(collections.Counter(sorted(list(input())))) for _ in range(N)]

print(int(sum(list(map(lambda x: x*(x-1)/2*1, list(collections.Counter(s).values()))))))

### FIXED CODE ###

import collections
N=int(input())
s=["".join(sorted(input())) for _ in range(N)]
print(int(sum(list(map(lambda x: x*(x-1)/2*1, collections.Counter(s).values())))))
### BUGGY CODE ###

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))

while m>0:
    max_a_ind=a.index(max(a))
    a[max_a_ind]=a[max_a_ind]//2
    m-=1

print(sum(a))


### FIXED CODE ###

from heapq import heappop,heappush,heapify
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7) 
 
n,m = map(int,input().split())
a = [int(x) for x in input().split()]
 
a_minus = [-x for x in a]
heapify(a_minus)
 
pop = lambda: -heappop(a_minus)
push = lambda x: heappush(a_minus,-x)
 
for _ in range(m):
    x = pop()
    push(x//2)
 
print(-sum(a_minus))
### BUGGY CODE ###

N=int(input())
a_min=1
b_min=1
for i in range(N):
  a,b=map(int,input().split())
  cnt=1
  while True:
    if a_min<=a*cnt and b_min<=b*cnt:
      break
    cnt+=1
  a_min=a*cnt
  b_min=b*cnt
print(a_min+b_min)

### FIXED CODE ###

import math
N=int(input())
min_a=1
min_b=1
for i in range(N):
  a,b=map(int,input().split())
  at=min_a//a
  if min_a%a!=0:
    at+=1
  bt=min_b//b
  if min_b%b!=0:
    bt+=1
  n=max(at,bt)
  min_a=a*n
  min_b=b*n
print(min_a+min_b)