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

import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
def main():
    n = ii()
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        u, v, w = mi()
        u -= 1
        v -= 1
        edge[u].append((v, w))
        edge[v].append((u, w))
    dist = [0]*n
    parent = [-1]*n
    que = deque([0])
    while que:
        v = que.pop()
        for nv, nx in edge[v]:
            if parent[nv] == v:
                continue
            parent[nv] = v
            dist[nv] = dist[v]+nx%2
            dist[nv]%= 2
            que.append(nv)
    print(*dist, sep='\n')
    


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
def main():
    n = ii()
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        u, v, w = mi()
        u -= 1
        v -= 1
        edge[u].append((v, w))
        edge[v].append((u, w))
    dist = [0]*n
    parent = [-1]*n
    que = deque([0])
    while que:
        v = que.pop()
        for nv, nx in edge[v]:
            if parent[v] == nv:
                continue
            parent[nv] = v
            dist[nv] = dist[v]+nx%2
            dist[nv]%= 2
            que.append(nv)
    print(*dist, sep='\n')
    


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

n = int(input())
i = 1
min_value = 10 ** 9 + 1
while i <= n:
    if n % i == 0:
        if max(len(str(i)),len(str(n // i))) > min_value:
            break
        min_value = min(min_value,max(len(str(i)),len(str(n // i))))
    i += 1
print(min_value)

### FIXED CODE ###

n = int(input())
i = 1
divisor = n ** 0.5
min_value = 10 ** 10 + 1
while i < divisor + 1:
    if n % i == 0:
        min_value = min(min_value,max(len(str(i)),len(str(n // i))))
    i += 1
print(min_value)
### BUGGY CODE ###

a,b,x = map(int,input().split())
s = range(a,b+1)
q = 0
for i in s:
  if i%x == 0:
    q += 1
    
print(q)

### FIXED CODE ###

def readinput():
    a,b,x=list(map(int,input().split()))
    return a,b,x
 
def main(a,b,x):
    ans = b//x - (a-1)//x
    return ans
 
if __name__=='__main__':
    a,b,x=readinput()
    ans=main(a,b,x)
    print(ans)
### BUGGY CODE ###


from collections import defaultdict

H, W, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

ctr_h = defaultdict(list)
ctr_w = defaultdict(list)

for h, w in X:
    ctr_h[h].append((h, w))
    ctr_w[w].append((h, w))

val_h = sorted(ctr_h.items(), key=lambda x: -len(x[1]))
val_w = sorted(ctr_w.items(), key=lambda x: -len(x[1]))

max_h = len(val_h[0][1])
max_w = len(val_w[0][1])

res = 0
for h, pairs_h in val_h:
    if len(pairs_h) < max_h:
        break

    for w, pairs_w in val_w:
        if len(pairs_w) < max_w:
            break

        cand = set()
        for point in pairs_h:
            cand.add(point)

        for point in pairs_w:
            cand.add(point)

        res = max(res, len(cand))

print(res)


### FIXED CODE ###


import sys
from collections import defaultdict

H, W, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

ctr_h = defaultdict(int)
ctr_w = defaultdict(int)
appeared = set()

for h, w in X:
    ctr_h[h] += 1
    ctr_w[w] += 1
    appeared.add(h * W + w)

val_h = sorted(ctr_h.items(), key=lambda x: -x[1])
val_w = sorted(ctr_w.items(), key=lambda x: -x[1])

max_h = val_h[0][1]
max_w = val_w[0][1]

val_h = [i for i, v in val_h if v == max_h]
val_w = [i for i, v in val_w if v == max_w]

if len(val_h) * len(val_w) > M:
    print(max_h + max_w)
    sys.exit(0)

for h in val_h:
    for w in val_w:
        if h * W + w not in appeared:
            print(max_h + max_w)
            sys.exit(0)
else:
    print(max_h + max_w - 1)
### BUGGY CODE ###

n,a=int(input()),list(map(int,input().split()));c=[a.count(i+1)for i in range(3)];x=[1/i for i in range(1,n+1)];dp=[[[0]*(n+2) for i in range(n+2)]for i in range(n+2)]
for k in range(n+1):
  for j in range(n-k+1):
    for i in range(n-k-j+1):
      if n+1>i+j+k>0:dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]])

### FIXED CODE ###

n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[None]*(z+2) for i in range(n-x+2)]for i in range(n+2)];dp[0][0][0]=0
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)
print(dp[x][y][z])
### BUGGY CODE ###

import math
ans = 0
n = int(input())
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans += math.gcd(i,math.gcd(j,k))
print(ans)

### FIXED CODE ###

k = int(input())
li=[1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692]
print(li[k-1])
### BUGGY CODE ###

import itertools

H,W,M=map(int,input().split())
l=[]
nh=[0]*H
nw=[0]*W
for _ in range(M):
    h,w=map(int,input().split())
    h-=1
    w-=1
    l.append((h,w))
    nh[h]+=1
    nw[w]+=1
hmax=max(nh)
wmax=max(nw)
is_h=[i for i in range(H) if nh[i]==hmax]
is_w=[i for i in range(W) if nw[i]==wmax]

for i_h,i_w in itertools.product(is_h,is_w):
    if not ((i_h,i_w) in l):
        print(hmax+wmax)
        break
else:
    print(hmax+wmax-1)

### FIXED CODE ###

import itertools

H,W,M=map(int,input().split())
d={}
nh=[0]*H
nw=[0]*W
for _ in range(M):
    h,w=map(int,input().split())
    h-=1
    w-=1
    d[(h,w)]=1
    nh[h]+=1
    nw[w]+=1
hmax=max(nh)
wmax=max(nw)
is_h=[i for i in range(H) if nh[i]==hmax]
is_w=[i for i in range(W) if nw[i]==wmax]

for i_h,i_w in itertools.product(is_h,is_w):
    if (i_h,i_w) not in d:
        print(hmax+wmax)
        break
else:
    print(hmax+wmax-1)
### BUGGY CODE ###

# writer解(c++)を写経した．answerのfor文のところ何やってるかさっぱりわかりませんが…
# https://atcoder.jp/contests/m-solutions2020/submissions/15122924
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        a, b, c = (int(i) for i in input().split())
        X.append(a)
        Y.append(b)
        P.append(c)
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    # bit 001001 とかの1が立っている集落に道を作る
    for bit in range(1 << N):
        for i in range(N):
            X_dist[bit][i] = P[i]*abs(X[i])
            Y_dist[bit][i] = P[i]*abs(Y[i])
            for k in range(N):
                if bit & (1 << k):
                    X_dist[bit][i] = \
                        min(X_dist[bit][i], P[i]*abs(X[i] - X[k]))
                    Y_dist[bit][i] = \
                        min(Y_dist[bit][i], P[i]*abs(Y[i] - Y[k]))

    # これはなに？
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        for j in range(i+1)[::-1]:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# writer解(c++)を写経した．answerのfor文のところ何やってるかさっぱりわかりませんが…
# https://atcoder.jp/contests/m-solutions2020/submissions/15122924
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        a, b, c = (int(i) for i in input().split())
        X.append(a)
        Y.append(b)
        P.append(c)
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    # bit 001001 とかの1が立っている集落に道を作る
    for bit in range(1 << N):
        for i in range(N):
            X_dist[bit][i] = P[i]*abs(X[i])
            Y_dist[bit][i] = P[i]*abs(Y[i])
            for k in range(N):
                if bit & (1 << k):
                    X_dist[bit][i] = \
                        min(X_dist[bit][i], P[i]*abs(X[i] - X[k]))
                    Y_dist[bit][i] = \
                        min(Y_dist[bit][i], P[i]*abs(Y[i] - Y[k]))

    # これはなに？
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


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

import numpy as np

x = int(input())

ans=0

for a in range(1,x+1):
    for b in range(a,x+1):
        for c in range(b,x+1):
            if a==b and b==c:
                ans += np.gcd.reduce([a,b,c])
            elif a==b or b==c or c==a:
                ans += 3*np.gcd.reduce([a,b,c])
            else:
                ans += 6*np.gcd.reduce([a,b,c])

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

def gcd(p,q): #p<q
    if q%p==0:
        return p
    return gcd(q%p,p)

x = int(input())

ans=0

for a in range(1,x+1):
    for b in range(1,a+1):
        for c in range(1,b+1):
            gcd1=gcd(a,b)
            gcd2=gcd(gcd1,c)
            if a==b and b==c:
                ans += gcd2
            elif a==b or b==c or c==a:
                ans += 3*gcd2
            else:
                ans += 6*gcd2

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

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

multi = 1
for i in range(n):
    multi = multi * a[i]

print(multi if multi <= 10 ** 18 else -1)

### FIXED CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))

if 0 in a:
    print(0)
    sys.exit()

else:
    multi = 1
    for i in a:
        multi *= i
        if multi > 10 ** 18:
            print(-1)
            sys.exit()

    print(multi)
### BUGGY CODE ###

a,b = map(int,input().split())
for i in range(a + 1,b + 1):
  a = (a ^ i)
print(a)

### FIXED CODE ###

a,b = map(int,input().split())

n = b - a + 1


if n % 2 == 0:
  if a % 2 == 1:
    ans = a ^ (((n - 2) // 2) % 2) ^ b
  else:
    m = n // 2
    ans = (m + 1) % 2 ^ 1
else:
  nn = (n - 1) // 2
  if a % 2 == 1:
    ans = (nn % 2) ^ a
  else:
    ans = (nn % 2) ^ b
    
print(ans)
### BUGGY CODE ###

#%%
import copy, math, collections

n = int(input())
a = input().split()

result = []

num_dict = dict(collections.Counter(a))

def calc(x):
    if x >= 2:
        return math.factorial(x) / (math.factorial(x - 2) * 2)
    else:
        return 0

result_dict = {}
result_minus1_dict = {}

for key in num_dict.keys():
    result_dict[key] = calc(num_dict[key])
    result_minus1_dict[key] = calc(num_dict[key] - 1)

for i in range(len(a)):
    result = 0

    for key, value in result_dict.items():
        if key == a[i]:
            result += result_minus1_dict[a[i]]
        else:
            result += value

    print(int(result))


# %%


### FIXED CODE ###

#%%
import copy, math, collections

n = int(input())
a = input().split()

result = []

num_dict = dict(collections.Counter(a))

def calc(x):
    if x >= 2:
        return math.factorial(x) / (math.factorial(x - 2) * 2)
    else:
        return 0

result_dict = {}
result_minus1_dict = {}

for key, value in num_dict.items():
    result_dict[key] = calc(num_dict[key])
    result_minus1_dict[key] = calc(num_dict[key] - 1)

result_all = sum(result_dict.values())

for i in range(len(a)):
    print(int(result_all - result_dict[a[i]] + result_minus1_dict[a[i]]))

# %%
### BUGGY CODE ###

import bisect
n = int(input())
k = []
for _ in range(3):
    a = [int(i) for i in input().split()]
    a.sort()
    k.append(a)
count = 0
for i in k[0]:
    b = bisect.bisect_right(k[1],i)
    for j in k[1][b:n]:
        c = bisect.bisect_right(k[2],j)
        count += n-c 
print(count)


### FIXED CODE ###

import bisect
n = int(input())
k = []
for _ in range(3):
    a = [int(i) for i in input().split()]
    a.sort()
    k.append(a)
count = 0
for i in k[1]:
    b = bisect.bisect_left(k[0],i)
    c = bisect.bisect_right(k[2],i)
    count += b*(n-c)
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int, [input() for i in range(n)]))

maxa=max(a)

for i in range(n):
    if a[i]==maxa:
        list = a[:]
        list.pop(i)
        list.sort(reverse=True)
        print(list[0])
    else:
        print(maxa)

### FIXED CODE ###

n = int(input())
a = list(map(int, [input() for i in range(n)]))

list=a[:]
list.sort(reverse=True)
max1 = list[0]
max2 = list[1]

for i in range(n):
    if a[i]==max1:
        print(max2)
    else:
        print(max1)
### BUGGY CODE ###

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=lambda x:x[1])
for i in range(N):
    xy[i][1] = i
xy.sort()

mod = 998244353
p2 = [1]*(N+1)
for i in range(N):
    p2[i+1] = p2[i]*2%mod

bit = BIT(N)

ans = 0

for i in range(N):
    y = xy[i][1]
    bit.add(y,1)
    n1 = i+1-bit.sum(y)
    n2 = i-n1
    n3 = N-y-1-n1
    n4 = N-i-1-n3
    ans += 1
    ans += (p2[n1]-1)+(p2[n2]-1)+(p2[n3]-1)+(p2[n4]-1)
    ans += (p2[n1]-1)*(p2[n2]-1)+(p2[n3]-1)*(p2[n4]-1)+(p2[n1]-1)*(p2[n3]-1)+(p2[n2]-1)*(p2[n4]-1)+2*(p2[n1]-1)*(p2[n4]-1)+2*(p2[n2]-1)*(p2[n3]-1)
    ans += 2*((p2[n1]-1)*(p2[n2]-1)*(p2[n3]-1)+(p2[n1]-1)*(p2[n2]-1)*(p2[n4]-1)+(p2[n1]-1)*(p2[n3]-1)*(p2[n4]-1)+(p2[n2]-1)*(p2[n3]-1)*(p2[n4]-1))
    ans += 2*(p2[n1]-1)*(p2[n2]-1)*(p2[n3]-1)*(p2[n4]-1)
    ans %= mod
print(ans)

### FIXED CODE ###

from operator import itemgetter

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=itemgetter(1))
for i in range(N):
    xy[i][1] = i+1
xy.sort(key=itemgetter(0))

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod

bit = BIT(N)
for i in range(N):
    l1 = bit.sum(xy[i][1])
    l2 = i-l1
    r1 = xy[i][1]-l1-1
    r2 = N-xy[i][1]-l2
    bit.add(xy[i][1],1)
    ans += (pow2[l2]-1)*(pow2[r1]-1)*pow2[r2]*pow2[l1]
    ans += (pow2[r2]-1)*(pow2[l1]-1)*(pow2[l2]+pow2[r1]-1)
    ans %= mod

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

def solve(maze,H, W, S, G):
    next_ = [S]
    seen = [[False]*W for _ in range(H)]
    n = 0
    while True:
        curr_ = next_[:]
        next_ = []
        for x in curr_:
            if seen[x[0]][x[1]]:
                continue
            seen[x[0]][x[1]] == True
            if x == G:
                return n
            move_to = [(x[0]+1, x[1]), (x[0], x[1]+1), (x[0]-1, x[1]), (x[0], x[1]-1)] 
            for m in move_to:
                h, w = m
                if 0 <= h < H and 0<= w < W:
                    if maze[h][w]:
                        next_.append(m)
        n += 1
    
    return print('error')

H, W = list(map(int, input().split()))
maze = [[True]*W for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            maze[h][w] = False

ans = 0
for i in range(H*W-1):
    for j in range(i+1, H*W):
        S = (i//W, i%W)
        G = (j//W, j%W)
        if maze[S[0]][S[1]] and maze[G[0]][G[1]]:
            ans = max(ans, solve(maze, H, W, S, G))

print(ans)

### FIXED CODE ###

def solve(maze,H, W, S):
    next_set = set()
    next_set.add(S)
    seen = [[False]*W for _ in range(H)]
    n = 0
    while next_set:
        n += 1
        curr_ = list(next_set)
        next_set = set()
        for h, w in curr_:
            if seen[h][w]:
                continue
            seen[h][w] = True
            for nh, nw in maze[h][w]:
                if seen[nh][nw] == False:
                    next_set.add((nh, nw))
    return n-1

# 入力
H, W = list(map(int, input().split()))
maze = [[[] for _ in range(W)] for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            maze[h][w] = False


# mazeに移動可能移動可能なマスを記録
for h in range(H):
    for w in range(W):
        if maze[h][w] == False:
            continue
        for nh, nw in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
            if 0 <= nh < H and 0<= nw < W:
                if maze[nh][nw] != False:
                    maze[h][w].append((nh, nw))
        # print(maze)
# print(maze)
ans = 0
for i in range(H*W-1):
        h = i//W
        w = i%W
        if maze[h][w]:
            ans = max(ans, solve(maze, H, W, (h, w)))

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

K,S = map(int,input().split())

count = 0
for X in range(K + 1):
  for Y in range(K + 1):
    for Z in range(K + 1):
      if X + Y + Z == S:
        count += 1

print(count)

### FIXED CODE ###

K,S = map(int,input().split())

result = 0
for X in range(K + 1):
  YZ = S - X
  if 0 <= YZ <= K:
    result += YZ + 1
  elif K < YZ <= 2 * K:
    result += 2 * K + 1 - YZ
  
print(result)
### BUGGY CODE ###

INF = 10**18

N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()] + [0]*100

dp = [INF] * 100200
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))

print(dp[N-1])

### FIXED CODE ###

N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

INF = 10**9

dp = [INF]*100010

dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        if i < N-j: dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))

print(dp[N-1])
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0
a = list(range(1,k+1))
b = list(range(1,k+1))
c = list(range(1,k+1))

for i in a:
    for j in b:
        for k in c:
            ans += gcd(i,j,k)
print(ans)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0
a = list(range(1,k+1))
b = list(range(1,k+1))
c = list(range(1,k+1))

for i in a:
    for j in b:
        for k in c:
            ans += gcd(i,j,k)
print(ans)
### BUGGY CODE ###

from math import sqrt
N = int(input())
S = 0
def f(n):
  ctr = 0
  for j in range (1, n+1//2 + 1):
    if n%j == 0:
      ctr += 1
  return ctr
for i in range (1, N+1):
  ctr = f(i)
  S += i*ctr
print(S)


### FIXED CODE ###

import math
N = int(input())
 
cnt = 0
for i in range(1, int(math.sqrt(N)+1)):
    sub = N//i
    cnt += (sub-i+1)*(sub+i)*i - i**2
cnt = int(cnt)
print(cnt)
### BUGGY CODE ###

import heapq
n, m = map(int, input().split())
A = list(map(lambda x: int(x)*-1, input().split()))

for i in range(m):
  heapq.heapify(A)
  max_elm = heapq.heappop(A)*-1 //2
  heapq.heappush(A, max_elm*-1)

ans = 0
for a in A:
  ans += a*-1
print(ans)

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
A = list(map(lambda x: int(x)*-1, input().split()))
heapq.heapify(A)

for i in range(m):
  max_elm = heapq.heappop(A)*-1 //2
  heapq.heappush(A, max_elm*-1)

print(sum(A)*-1)
### BUGGY CODE ###

import sys

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

if __name__ == "__main__":
    n = int(input())
    al = [int(input()) for i in range(n)]

    for i in range(n):
        print(max(al[:i] + al[i+1:]))


### FIXED CODE ###

import sys
from operator import itemgetter

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

if __name__ == "__main__":
    n = int(input())
    al = [(i, int(input())) for i in range(n)]

    al.sort(key = itemgetter(1), reverse = True)

    for i in range(n):
        print(al[0][1] if i != al[0][0] else al[1][1])
### BUGGY CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
import sys
sys.setrecursionlimit(10**6)
mod=998244353
n=i1()
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=max(t[i*2+1],t[i*2+2])

def qr(a,b,k,l,r):
  if r<=a or b<=l:
     return -1
  elif a<=l and r<=b:
     return t[k]
  else:
     return max(qr(a,b,k*2+1,l,(l+r)//2),qr(a,b,k*2+2,(l+r)//2,r))

for i in range(n):
  d.append(i2())
d=sorted(d)
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
r=[]
for i in range(n):
 j=bisect.bisect_left(dx,dx[i]+dd[i])-1
 r.append(j)

for i in range(n)[::-1]:
 tt=qr(i,r[i]+1,0,0,N)
 ud(i,max(r[i],tt))
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)>>1
    if t[i*2+1]>t[i*2+2]:t[i]=t[i*2+1]
    else:t[i]=t[i*2+2]
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         if L<t[a]:L = t[a]
      if b&1==0:
         b-=1
         if R<t[b]:R = t[b]
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d.sort()
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 tx=dx[i]+dd[i]
 j=bisect.bisect_left(dx,tx)
 tt=qr(i,j)
 if j-1>tt:ud(i,j-1)
 else:ud(i,tt)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])
### BUGGY CODE ###

N = int(input())

ans = 0
i = 0
while True:
    x = (2 * 5 * (5 ** i))
    if x <= N:
        ans += N // x
        i += 1

print(ans)

### FIXED CODE ###

N = int(input())

ans = 0
if N % 2 == 0:
    i = 0
    while True:
        x = (2 * 5 * (5 ** i))
        if x > N:
            break
        ans += N // x
        i += 1

print(ans)