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

def primes(x):
    p = set()
    for i in range(2, x + 1):
        if x == 1:
            break
        if x % i != 0:
            continue
        while x % i == 0:
            x = x // i
        else:
            p.add(i)

    return p


def main():
    n, *a, = map(int, open(0).read().split())
    b = set()
    c = primes(a[0])
    f = True
    for i in a:
        p = primes(i)
        if f:
            if b & p:
                f = False
            b = b.union(p)
        c = c & p

    if f:
        ans = "pairwise coprime"
    elif len(c) == 0:
        ans = "setwise coprime"
    else:
        ans = "not coprime"

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, *a, = map(int, open(0).read().split())
    m = max(a)

    d = [0] * (m+1)
    d[1] = 1
    for i in range(2, m+1):
        for j in range(i, m+1, i):
            if d[j] == 0:
                d[j] = i

    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    c = primes(a[0])
    f = 1
    for i in a:
        ps = set()
        while i != 1:
            p = d[i]
            ps.add(p)
            i = i // d[i]
        if f:
            if b & ps:
                f = 0
            b |= ps
        c &= ps

    if f:
        ans = "pairwise coprime"
    elif len(c) == 0:
        ans = "setwise coprime"
    else:
        ans = "not coprime"

    print(ans)


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

# coding: utf-8
# Your code here!
N,K=map(int,input().split())
l=list(map(int,input().split()))

if max(l)<K:
    print("IMPOSSIBLE")
    exit()

temp=[]
prev_l=[-1]

while prev_l!=l: #temp <=> l
    temp.clear()
    prev_l.clear()
    prev_l=prev_l+l
    for i in range(len(l)-1):
        for j in range(i+1,len(l)):
            temp.append(abs(l[i]-l[j]))
    l=l+temp
    l=list((set(l)))
    for i in range(len(l))[::-1]:
        if l[i]>K:
            for j in range(i)[::-1]:
                if (l[i]-K)%l[j]==0:
                    print("POSSIBLE")
                    exit()
        elif l[i]==K:
            print("POSSIBLE")
            exit()
        else:
            break
    
print("IMPOSSIBLE")

### FIXED CODE ###

# coding: utf-8
# Your code here!
from fractions import gcd
from functools import reduce

N,K=map(int,input().split())
l=list(map(int,input().split()))

if max(l)<K:
    print("IMPOSSIBLE")
else:
    if K%reduce(gcd, l)==0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
### BUGGY CODE ###

b, w = map(int, input().split())
MOD = 10 ** 9 + 7
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

def calc(y, x):
	return (y * pow(x, MOD-2, MOD)) % MOD

ans = 500000004
print(ans)
for i in range(1, b+w):
	if i-1 >= b-1:
		ans -= calc(comb(i-1, b-1), pow(2, i+1))
	if i-w >= 0:
		ans += calc(comb(i-1, i-w), pow(2, i+1))
	ans %= MOD
	print(ans)


### FIXED CODE ###

b, w = map(int, input().split())
MOD = 10 ** 9 + 7
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

two_pow = [1]
for i in range(b+w+1):
	two_pow.append((two_pow[-1] * 500000004) % MOD)

ans = 500000004
print(ans)
for i in range(1, b+w):
	if i-1 >= b-1:
		ans -= comb(i-1, b-1) * two_pow[i+1]
	if i-w >= 0:
		ans += comb(i-1, i-w) * two_pow[i+1]
	ans %= MOD
	print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
revcount = 0

ans = S
ansf = []
ansb = []
T = [0,0,""]
for i in range(Q):
  TS = input()
  if TS == "1":
    revcount += 1
  else:
    T = TS.rstrip().split(" ")
    if (int(T[1]) == 1 and revcount % 2 == 0) or (int(T[1]) == 2 and revcount % 2 == 1):
      ansf.insert(0,T[2])
    else:
      ansb.append(T[2])
      
ansff = "".join(ansf)
ansbb = "".join(ansb)

ans2 = ansff + ans + ansbb

if revcount % 2 == 1:
  print(ans2[::-1])
else:
  print(ans2)

### FIXED CODE ###

S = list(input())
mae = []
ato = []
rev = False
Q = int(input())
for i in range(Q):
    A = list(input().rstrip().split(" "))
    if int(A[0]) == 1:
        if rev:
            rev = False
        else:
            rev = True
    else:
        if (rev and int(A[1]) == 2 or not rev and int(A[1]) == 1):
            mae.append(A[2])
        else:
            ato.append(A[2])
if rev:
    ato.reverse()
    S.reverse()
    print("".join(ato) + "".join(S) + "".join(mae))
else:
    mae.reverse()
    print("".join(mae) + "".join(S) + "".join(ato))
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ls = [0] * n
    mt = [0] * n
    cnt = 0
    for w in range(10 ** 15):
        cnt += 1
        f = [False] * n
        cc = 0
        
        for i in range(n):
            if ls[i] != -1:
                mt[i] = a[i][ls[i]]
                cc += 1
        for i in range(n):
            if not f[i]:
                if ls[i] != -1:
                    if i + 1 == mt[mt[i]-1]:
                        cc -= 2
                        f[i] = True
                        f[mt[i]-1] = True
            if cc == 0:
                break
        bb = False
        for i in range(n):
            if f[i]:
                if ls[i] + 1 < n - 1:
                    ls[i] += 1
                    bb = True
                else:
                    ls[i] = -1
        b = True
        for i in range(n):
            if ls[i] != -1:
                b = False
                break
        if b:
            print(cnt)
            exit()
        if not bb:
            print(-1)
            exit()


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ad = [0] * n
    dq = collections.deque([[0, i + 1] for i in range(n)])
    for i in range(10 ** 15):
        fd = {}
        while True:
            if len(dq) != 0:
                d, q = dq.popleft()
                q -= 1
                if d <= i:
                    if ad[q] < n - 1:
                        qq = a[q][ad[q]] - 1
                        tq = a[qq][ad[qq]] - 1
                        if q == tq and qq not in fd and tq not in fd:
                            ad[qq] += 1
                            ad[tq] += 1
                            if ad[qq] < n - 1:
                                dq.append([d + 1, qq + 1])
                            if ad[tq] < n - 1:
                                dq.append([d + 1, tq + 1])
                            fd[qq] = 0
                            fd[tq] = 0
                else:
                    dq.append([d, q + 1])
                    break
            else:
                break
        if len(dq) == 0:
            b = True
            for v in ad:
                if v != n - 1:
                    b = False
                    break
            if b:
                print(i + 1)
                exit()
            else:
                print(-1)
                exit()


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

from queue import Queue
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(input()))
tx = [1,0,-1,0]
ty = [0,1,0,-1]
cnt = 0
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '#':
            cnt += 1
q = Queue()
q.put([0,0,1])
flag = 1
while not q.empty():
    x, y, index = q.get()
    MAP[x][y] = '#'
    if x == H - 1 and y == W - 1:
        flag = 0
        cnt += index
        break
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and MAP[nx][ny] == '.':
            q.put([nx,ny,index+1])
if flag:
    print(-1)
else:
    ans = H * W - cnt
    print(ans)

### FIXED CODE ###

from queue import Queue
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(input()))
tx = [1,0,-1,0]
ty = [0,1,0,-1]
cnt = 0
INF = 10 ** 8
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '#':
            cnt += 1
d = [[INF for i in range(W)] for j in range(H)]
q = Queue()
q.put([0,0])
d[0][0] = 1
flag = 1
while not q.empty():
    x, y = q.get()
    if x == H - 1 and y == W - 1:
        flag = 0
        break
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and MAP[nx][ny] == '.' and d[nx][ny] == INF:
            d[nx][ny] = d[x][y] + 1
            q.put([nx,ny])
if flag:
    print(-1)
else:
    ans = H * W - d[H-1][W-1] - cnt
    print(ans)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


n, m = map(int, input().split())
uf = UnionFind(n)

for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

ans = 0
for l in list(uf.all_group_members().values()):
    ans = max(ans, len(l))

print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n=0):
        self.d = [-1]*n
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.d[self.find(x)]


n, m = map(int, input().split())
uf = UnionFind(n)

for _ in range(m):
    a, b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))

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

N = int(input())
a = list(map(int, input().split()))
L = list(set(a))
res = 0

for i in L:
    if a.count(i) < i:
        res += a.count(i)
    
    else:
        res += a.count(i) - i

print(res)
    
  

### FIXED CODE ###

from collections import Counter
N = int(input())
a = list(map(int, input().split()))
L = list(set(a))
res = 0
d = Counter()
d.update(a)
for i in L:
    X = d[i]
    if X < i:
        res += X
    
    else:
        res += X - i

print(res)
### BUGGY CODE ###

string = input()

start_length = len(string)

while len(string) > 0:
  if "10" in string or "01" in string:
    string = string.replace("10", "")
    string = string.replace("01", "")
  else:
    break

print(start_length - len(string))


### FIXED CODE ###

s = input()

start_len = len(s)

num_1 = s.count("1")
num_0 = s.count("0")

end_len = abs(num_1 - num_0)

print(abs(end_len - start_len))
### BUGGY CODE ###

K = int(input())
cnt = 10
i = 10
lunlun_nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
if cnt > K:
    output = K
else :
    while cnt < K:
        i += 1
        if i//10 in lunlun_nums:
            num = list(map(int,[l for l in str(i)]))
            if abs(num[-2] - num[-1]) <= 1:
                lunlun_nums.add(i)
                cnt += 1
    output = i
print(output)


### FIXED CODE ###

from collections import deque

q = deque(range(1,10))
K = int(input())

for i in range(K):
    x = q.popleft()
    r =  x % 10
    if r != 0:
        q.append((10 * x) + (r - 1))
    q.append((10 * x) + r)
    if r != 9:
        q.append((10 * x) + (r + 1))

print(x)
### BUGGY CODE ###

n, a = map(int, input().split())
l = [int(i) for i in input().split()]

dp = [[[0] * 2501 for j in range(51)] for i in range(51)]

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

for i in range(n):
    for j in range(51):
        for k in range(2501):
            if k >= l[i] and j >= 1:
                dp[i+1][j][k] = dp[i][j][k] + dp[i][j-1][k-l[i]]
            else:
                dp[i+1][j][k] = dp[i][j][k]

print(sum([dp[n][m][a*m] for m in range(1, n+1)]))

### FIXED CODE ###

n, a = map(int, input().split())
l = [int(i) for i in input().split()]

dp = [[[0] * 2501 for j in range(51)] for i in range(51)]

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

for i in range(n):
    for j in range(51):
        for k in range(2501):
            if k >= l[i] and j >= 1:
                dp[i+1][j][k] = dp[i][j][k] + dp[i][j-1][k-l[i]]
            else:
                dp[i+1][j][k] = dp[i][j][k]

print(sum([dp[n][m][a*m] for m in range(1, n+1)]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = list(input())
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                d -= 1
                dm -= m
            elif S[j] == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            ret += dm
            
    print(ret)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)
### BUGGY CODE ###


S = input()
Q = int(input())

# 逆フラグ
r = 1  # 1==正
for q in range(Q):
  s = input()
  if len(s) == 1:
    r *= -1
  else:
    s, f, c = s.split()
    if f == '1':
      if r == 1:
        S = c + S
      else:
        S = S + c
    else:
      if r == 1:
        S = S + c
      else:
        S = c + S
if r == -1:
  S = S[::-1]
print(S)

### FIXED CODE ###

from collections import deque
d = deque(input())
Q = int(input())

# 逆フラグ
r = 1  # 1==正
for q in range(Q):
  s = input()
  if len(s) == 1:
    r *= -1
  else:
    s, f, c = s.split()
    if (f == '1' and r == -1) or (f == '2' and r == 1):
      d.append(c)
    else:
      d.appendleft(c)
ans = ''.join(d)
if r == -1:
  #d = d[::-1]
  print(ans[::-1])
else:
  print(ans)
### BUGGY CODE ###

S = list(input())
ans = ['1'] * len(S)
# split_num = [0]
# for i, s in enumerate(S[1:-1]):
#     if S[i-1] == "L" and S[i+1] == "R":
#         ans[i] = 0
#         split_num.append(i)
# split_num.append(len(S))
#
# for i in range(len(split_num)-1):
#     pre_ans = [1] * len(S[split_num[i]:split_num[i+1]])
#     for i, s in enumerate(S[split_num[i]:split_num[i+1]]):
#         print(s)

import copy
pre_ans = ['1'] * len(S)
pre_pre_ans = ['1'] * len(S)
flag = 0
# while True:
for _ in range(10 ** 5):
    ans[0] = '0'
    ans[-1] = '0'
    if S[1] == 'L':
        ans[0] = pre_ans[1]
    if S[-2] == "R":
        ans[-1] = pre_ans[-2]
    for i, s in enumerate(S[1:-1]):
        ans[i+1] = '0'
        if S[i] == 'R' and S[i+2] == "L":
            ans[i+1] = str(int(pre_ans[i]) + int(pre_ans[i+2]))
        elif S[i] == 'R':
            ans[i+1] = pre_ans[i]
        elif S[i+2] == 'L':
            ans[i+1] = pre_ans[i+2]
    if ans == pre_ans:
        flag = 1
        break
    elif ans == pre_pre_ans:
        flag = 2
    pre_pre_ans = copy.deepcopy(pre_ans)
    pre_ans = copy.deepcopy(ans)

if flag == 1:
    print(' '.join(ans))
elif flag == 2:
    print(' '.join(pre_ans))


### FIXED CODE ###

s = input()
tmp = [0]
for i in range(len(s)-1):
    if s[i] != s[i+1]:  # RとLが切り替わる時のインデックスを保存
        tmp.append(i+1)
tmp.append(len(s))
ans = [0 for i in range(len(s))]
for i in range(len(tmp)-1):
    if i % 2 == 1:
        ans[tmp[i]] = (tmp[i]-tmp[i-1])//2 + (tmp[i+1]-tmp[i]+1)//2
        ans[tmp[i]-1] = (tmp[i+1]-tmp[i])//2 + (tmp[i]-tmp[i-1]+1)//2
print(*ans)
# RRLLLLRLRRLL
### BUGGY CODE ###

n = int(input())
count = 0
def gcd(a,b):
    c = max(a,b)
    d = min(a,b)
    if b == 0:
        return a
    return gcd(b,a%b)

for i in range(1,n+1):

    i_str = str(i)
    if i_str[0]=='3' or i_str[0]=='5' or i_str[0]=='7':
        three = i_str.count('3')
        five = i_str.count('5')
        seven = i_str.count('7')
        sum_number = three + five + seven
        if len(i_str) == sum_number and three>0 and five>0 and seven>0:
            count += 1

print(count)


### FIXED CODE ###

n = int(input())
ans = []
count = 0
def dfs(s):

    if int(s)>n:
        return 0
    ans.append(s)
    for c in '753':
        dfs(s+c)
dfs('0')
for i in ans:
    if all(i.count(j)>0 for j in '753'):
        count += 1
print(count)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
l=[a[0]]
ans=0
for aa in a[1:]:
  ans+=max(l)
  l.remove(max(l))
  l.append(aa)
  l.append(aa)
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=a[0]
w=n//2
for aa in a[1:w]:
  ans+=aa*2
if n%2!=0:
  ans+=a[w]
print(ans)
### BUGGY CODE ###

N = int(input())

s = [sorted(list(input())) for i in range(N)]

for i in range(N):
    s[i] = ''.join(s[i])

ss = set(s)
ans = 0

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

print(ans)


### FIXED CODE ###

import collections
N = int(input())

s = [sorted(list(input())) for i in range(N)]

for i in range(N):
    s[i] = ''.join(s[i])

ans = 0

c = collections.Counter(s)
for v in c.values():
    ans += (1/2) * v * (v-1)

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

n, k = [int(i) for i in input().split()]
while abs(n - k) < n:
        n = abs(n-k)
print(n)

### FIXED CODE ###

n, k = [int(i) for i in input().split()]

if n >= k:
    result = min(n % k, k - (n % k))
elif 2 * n >= k > n:
    n = abs(k - n)
    result = n
else:
    result = n

print(result)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
inf = float('inf')
dp = [inf] * N
dp[0] = 0

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

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
inf = float('inf')
dp = [inf] * N
dp[0] = 0

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

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

from collections import *
from copy import *
n=int(input())
a=sorted(list(map(int,input().split())))
l=Counter(a)
m=l.most_common()
f=[False for i in range(max(a)+1)]
ans=0
for i,j in m:
    t=deepcopy(i)
    if f[t]==False and j==1:
               
        ans+=1
        while t<=max(a):
            f[t]=True
            t+=i
    elif f[t]==False and j!=1:
        while t<=max(a):
            f[t]=True
            t+=i
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
dp=[0]*(a[-1]+1)

for i in a :
    dp[i]+=1

for i in a :
    if dp[i] :
        for j in range(i*2,a[-1]+1,i) :
            dp[j]=0

print(dp.count(1))
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            k1=S[j+1:].count(S[i])
            k2=S[j+1:].count(S[j])
            ans=ans+len(S[j+1:])-k1-k2
        if j+(j-i)<N and S[i]!=S[j]:
            if S[j+(j-i)]!=S[i] and S[j+(j-i)]!=S[j]:
                ans-=1
            
print(ans)

### FIXED CODE ###

def main():
    N=int(input())
    S=input()
    k1=S.count("R")
    k2=S.count("B")
    ans=k1*k2*(len(S)-k1-k2)
    for i in range(N-2):
        for j in range(i+1,N-1):
            if j+(j-i)<N and S[i]!=S[j]:
                if S[j+(j-i)]!=S[i] and S[j+(j-i)]!=S[j]:
                    ans-=1
    print(ans)
main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

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')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

A = list(map(int, input()))
N = len(A)
mod = 2019

dp0 = list2d(N+1, mod, 0)
dp1 = list2d(N+1, mod, 0)
dp2 = list2d(N+1, mod, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    dp0[i+1][0] = dp0[i][0]
    dp1[i+1][a] = dp0[i][0]
    for j in range(mod):
        nxt = (j*10+a) % mod
        dp1[i+1][nxt] += dp1[i][j]
        dp2[i+1][nxt] += dp1[i][j]
        dp2[i+1][j] += dp2[i][j]
ans = dp2[N][0]
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import Counter

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')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

acc = [0] * (N+1)
mul = 1
for i in range(N-1, -1, -1):
    x = int(S[i]) * mul
    acc[i] = (acc[i+1] + x) % mod
    mul *= 10
    mul %= mod

C = Counter(acc)
ans = 0
for v in C.values():
    ans += v*(v-1) // 2
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(M)]

ans = 0
t = 0

for i in range(N): 
    t = 1
    for j in range(M):
        if not li[j][0] <= i+1 <= li[j][1]:
            t = 0
            break
    ans += t

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
L = []
R = []
ans = 0

for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
L_max = max(L)
L_min = min(R)

for i in range(N):
    if L_max <= i+1 <= L_min:
        ans += 1
print(ans)