Harryxun/stf_run huggingface dataset:
a=int(input())
b=int(input())
l=[]
count=0
for i in range(2,min(a,b)+1):
  if a%i==0 and b%i==0:
    l.append(i)
for j in range(0,len(l)):
  for k in rage(0,j-1):
    
  if l[j+1]%l[k]!=0:
    count=count+1
print(count+1)
    

### FIXED CODE ###

from math import sqrt, ceil
 
a, b = map(int, input().split())
 
c_a = set()
c_b = set()
 
for i in range(1, ceil(sqrt(a))+1):
  if a % i == 0:
    c_a.add(i)
    if i > 1:
        while a % i == 0:
            a = a // i
if a != 1:
    c_a.add(a)
 
for j in range(1, ceil(sqrt(b))+1):
  if b % j == 0:
    c_b.add(j)
    if j > 1:
        while b % j == 0:
            b = b // j
if b != 1:
    c_b.add(b)
 
ans = c_a.intersection(c_b)
 
print(len(ans))
n = list(map(int, input().split()))
5count = 2
7count = 1
for i in range(len(n)):
    if n[i] == 5:
        5count -= 1
    elif n[i] == 7:
        7count -= 1
if 5count==0 and 7count==0:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

n = list(map(int, input().split()))
count_5 = 2
count_7 = 1
for i in range(len(n)):
    if n[i] == 5:
        count_5 -= 1
    elif n[i] == 7:
        count_7 -= 1
if count_5==0 and count_7==0:
    print('YES')
else:
    print('NO')
N = int(input())

ACcount = 0 
WAcount = 0
TLEcount = 0
REcount = 0
for i in range(N):
	S=input()

	if S == "AC":
		ACcount = ACcount + 1
	elif S == "WA":
		WAcount = WAcount + 1
	elif S == "TLE":
		TLEcount = TLEcount + 1
	elif S == "RE":
		REcount = REcount + 1

print("AC x", ACcount)
print("WA x", WAcount)
print("TLE x", TLEcount)
print("RE x", REcount)

### FIXED CODE ###

N = int(input())

if N % 1000 == 0:
	print(0)
else:
	print(1000 - (N % 1000))
n, d = map(int, input().split())
s == 0
for i in range(n+1):
	x, y = map(int, input().split())
	if x**2+y**2 <= d**2:
		s = s+1
print(s)

### FIXED CODE ###

n, d = map(int, input().split())
s = 0
for i in range(n):
	x, y = map(int, input().split())
	if x**2+y**2 <= d**2:
		s += 1
print(s)
a,b=map(int,input().split())
M = input()
l = M.split()
ll = list(map(int, l))
q=0
ans=1
for i in range(a):
  ai +=1
  q += ll[i]
  if q <= b :
    ans += 1
print(ans)


### FIXED CODE ###

a,b=map(int,input().split())
M = input()
l = M.split()
ll = list(map(int, l))
q=0
ans=1
for i in range(a):
  q += ll[i]
  if q <= b :
    ans += 1
print(ans)
A,B,C = map(int,input().split())
res = -A+B+C
if res <= 0:
  res = 0
return res

### FIXED CODE ###

A,B,C = map(int,input().split())
res = -A+B+C
if res <= 0:
  res = 0
print(res)
import sys
 
def main():
  N, W = map(int, input().split())
  w = [0]*N
  v = [0]*N
  for i in range(N):
          w[i], v[i] = map(int, sys.stdin.readline().split())

  #WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]


  dp = [[0]*(N+1) for j in range(W+1)]

  for i in range(1, W+1):
          for j in range(1, N+1):
                  if i - w[j-1]>=0:
                  #if i - WV[j-1][0]>=0:
                          dp[i][j] = max(dp[i-w[j-1]][j-1]+v[j-1], dp[i][j-1])
                          #dp[i][j] = max(dp[i-WV[j-1][0]][j-1]+WV[j-1][1], dp[i][j-1])
                  else:
                          dp[i][j] = dp[i][j-1]

  print(dp[W][N])

if __name__ == '__main__':
    main()

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))

dp = [0]*N

dp[1] = abs(H[1]-H[0])
for i in range(2, N):
    dp[i] =  min(dp[i-2]+abs(H[i]-H[i-2]), dp[i-1]+abs(H[i]-H[i-1]))

print(dp[N-1])
def union_find():
    # グラフの連結していないグループの数をunion_findで求める
    def get_parent(node):
        if par[node] == -1:
            return node
        else:
            par[node] = get_parent(par[node])
            return par[node]

    def merge(i, j):
        i = get_parent(i)
        j = get_parent(j)
        if i != j:
            par[j] = i
        return

    n, m = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(m)]
    par = [-1] * n
    for x, y in xy:
        merge(x-1, y-1)
    print(par.count(-1))


union_find()

### FIXED CODE ###

def union_find():
    # グラフの連結していないグループの数をunion_findで求める
    def get_parent(node):
        if par[node] == -1:
            return node
        else:
            par[node] = get_parent(par[node])
            return par[node]

    def merge(i, j):
        i = get_parent(i)
        j = get_parent(j)
        if i != j:
            par[j] = i
        return

    n, m = map(int, input().split())
    xyz = [list(map(int, input().split())) for _ in range(m)]
    par = [-1] * n
    for x, y, z in xyz:
        merge(x-1, y-1)
    print(par.count(-1))

union_find()
n = int(input())
if n==3 or n==5 or n==7:


### FIXED CODE ###

n = int(input())
if n==3 or n==5 or n==7:
    print('YES')
else:
    print('NO')
# -*- coding: utf-8 -*-
test = input()
a, b, c = map(int, test.split())  # 変数a,b,cにそれぞれN、A、Bをint型にして入力する　
x = []
for i in range(1,a+1):  # list型の変数xに１からNまでの要素を入れる
    x.append(i)


len_x = len(x)  # リスト型の変数xの要素数を獲得

d = 0  # リストの各行の和を入れるための変数
f = []  # 各行の和がA以上B以下の要素を入れるための変数
x = map(str, x)  # リストxの書く要素をstr型に変換

for i in range(len_x):
    e = x[i]           # xのi番目の要素を抽出
    e = list(e)  # xのi番目の要素を一文字ずつのstr型としてリスト型の変数に入れる
    e = map(int, e)  # xのi番目の要素をint型に変換
    e_number = len(e)  # リスト型の変数eの要素数を取得
    d = 0              # 位の合計の判定用の変数
    for g in range(e_number):
        d += e[g]  # 位の合計
    if b <= d <= c:  # 位の合計がA以上B以下ならリストfに要素を追加
        f.append(x[i])
answer = 0  # 条件位合う要素の合計を入れる変数
f = map(int, f)
for h in f:  # 要素に合う要素の合計
    answer += h
print(str(answer))




### FIXED CODE ###

# coding: utf-8
# Your code here!
#-*- coding: utf-8 -*-#
test = input()
a, b, c = map(int, test.split())  # 変数a,b,cにそれぞれN、A、Bをint型にして入力する　
x = []
e = []
for i in range(1,a+1):  # list型の変数xに１からNまでの要素を入れる
    x.append(i)
len_x = len(x)  # リスト型の変数xの要素数を獲得
d = 0  # リストの各行の和を入れるための変数
f = []  # 各行がA以上B以下の要素を入れるための変数
x = map(str, x) # リストxの各要素をstr型に変換
x = list(x)
e_number = 0
for i in range(len_x):
    e = x[i]           # xのi番目の要素を抽出
    e = list(e)  # xのi番目の要素を一文字ずつのstr型としてリスト型の変数に入れる
    e = map(int, e)# xのi番目の要素をint型に変換
    e = list(e)
    e_number = len(e)   # リスト型の変数eの要素数を取得
    d = 0              # 位の合計の判定用の変数
    for g in range(e_number):
        d += e[g-1]  # 位の合計
    if b <= d <= c:  # 位の合計がA以上B以下ならリストfに要素を追加
        f.append(x[i])
answer = 0  # 条件位合う要素の合計を入れる変数
f = map(int, f)
for h in f:
    answer += h  # 要素に合う要素の合計
print(answer)
n, m = list(map(int, input().split()))
city_list = [[] for i in range(n)]

for i in range(m):
    pm, ym = list(map(int, input().split()))
    city_list[pm-1].append(ym)
city_list_copied = copy.deepcopy(city_list)

for i in range(n):
    city_list_copied[i].sort()
    for j in range(len(city_list[i])):
        cindex = sum(x <= city_list[i][j] for x in city_list[i])
        print("{:0=6}{:0=6}".format(i+1, cindex))


### FIXED CODE ###

n, m = list(map(int, input().split()))
city_list = []

for i in range(m):
    pm, ym = list(map(int, input().split()))
    city_list.append([i,pm,ym])

city_count = {}
city = {}

for i,p,y in sorted(city_list, key=lambda x: x[2]):
    if not p in city_count:
        city_count[p] = 1
    else:
        city_count[p] += 1
    city[i,p] = city_count[p]

for i,p,y in city_list:
    print("{:0=6}{:0=6}".format(p, city[i,p]))
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

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


def solve():
    a = ri()
    print (a + a*a + a*a*a)





mode = 's'

if mode == 's':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()


### FIXED CODE ###

from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

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


def solve():
    a = ri()
    print (a + a*a + a*a*a)





mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()
N, M = map(int, input().split())
X = list(map(int, input().split()))
X.sort()

difX = []
for i in range(len(X)-1):
    difX.append(X[i+1]-X[i])


for i in range(N-1):
    difX.pop(difX.index(max(difX)))

total = 0
for x in difX:
    total+= x

print(total)

### FIXED CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))
X.sort()

difX = []
for i in range(len(X)-1):
    difX.append(X[i+1]-X[i])
difX.sort(reverse=True)

if M > N:

    difX = difX[N-1:]

    total = 0
    for x in difX:
        total+= x

    print(total)
else:
    print(0)
n,m = map(int,input().split())
s = input()
t = input()
#greatest common divisor/least common multiple
import math
gcd = math.gcd(n,m)
lcm = n*m/gcd
l = lcm/((m/gcd)(n/gcd))
counter=0
for i in range(l):
    if s[1+n/gcd]!=t[m/gcd]:
        print(-1)
        counter+=1
        exit()
if counter == 0:
    print(lcm)


### FIXED CODE ###

n,m = map(int,input().split())
s = input()
t = input()
#greatest common divisor/least common multiple
import fractions
gcd = int(fractions.gcd(n,m))
lcm = int(n*m/gcd)
counter=0
for i in range(gcd):
    if s[int(n/gcd)*i]!=t[int(m/gcd)*i]:
        print(-1)
        counter+=1
        exit()
if counter == 0:
    print(lcm)
def f(b):
	if b% 4 == 0 or b%4 == 3:
		ans2 = '0'
	else:
		ans2 = '1'
	for i in range(40)
		k = i+1
		c = b // (2**k)
		if c % 2 ==1 and B % 2 == 1:
			ans2 = '0'+ ans2
		else:
			ans2 = '1' + ans2
	return ans2

def add(x,y):
	c = 0
	for i in range(41)
		c += ((int(x[i]) + int(y[i]))%2) * (2**(40-i))
	return c
	
a,b = list(map(int,input().split()))
print(add(f(a),f(b)))

### FIXED CODE ###

def f(n):
	if n%4 == 3:
		return 0
	elif n%4 == 0:
		return n
	elif n%4 == 1:
		return 1
	else:
		return n+1

def xor(x,y):
	c = 0
	k = 0
	while 2**k < max(x,y)+1:
		c += (2**k) * ( (((x//(2**k))%2) + ((y//(2**k))%2)) %2 )
		k += 1
	return c

a,b = list(map(int,input().split()))
print(xor(f(a-1),f(b)))
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

t = [0] * (max(a) + 1)
for v in a:
    t[v] += 1

if max(a) <= 1:
    pritn(t[0] + t[1])
    sys.exit(0)

ans = 0
for i in range(0, max(a) - 1):
    ans = max(ans, t[i] + t[i+1] + t[i+2])

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

t = [0] * (max(a) + 1)
for v in a:
    t[v] += 1

if max(a) <= 1:
    print(sum(t))
    sys.exit(0)

ans = 0
for i in range(0, max(a) - 1):
    ans = max(ans, t[i] + t[i+1] + t[i+2])

print(ans)
a = str(input())

if a.count('a') % 2 == 0 and a.count('b') % 2 == 0 and a.count('c') % 2 == 0 and a.count('d') % 2 == 0
and a.count('e') % 2 == 0 and a.count('f') % 2 == 0 and a.count('g') % 2 == 0 and a.count('h') % 2 == 0
and a.count('i') % 2 == 0 and a.count('j') % 2 == 0 and a.count('k') % 2 == 0 and a.count('l') % 2 == 0
and a.count('m') % 2 == 0 and a.count('n') % 2 == 0 and a.count('o') % 2 == 0 and a.count('p') % 2 == 0
and a.count('q') % 2 == 0 and a.count('r') % 2 == 0 and a.count('s') % 2 == 0 and a.count('t') % 2 == 0
and a.count('u') % 2 == 0 and a.count('v') % 2 == 0 and a.count('w') % 2 == 0 and a.count('x') % 2 == 0
and a.count('y') % 2 == 0 and a.count('z') % 2 == 0:
    print('Yes')
    
else:
    print('No')



### FIXED CODE ###

w = input()
wd = list(set(w))
 
for word in wd:
    if w.count(word) % 2 != 0:
        print("No")
        break
else:
    print("Yes")
import numpy as np

N, M, K = list(map(int, input().split()))
A = list(map(int, [0] + input().split()))
B = list(map(int, [0] + input().split()))
cost = 0
ind_a = 0
ind_b = 0
dp = np.zeros((N + 3, M + 3)).astype(int)
cumsum_a = np.cumsum(A)
cumsum_b = np.cumsum(B)
max_book = 1
while True:
    for i in range(max_book + 1):
        if max_book - i <= N and i <= M:
            if K >= cumsum_a[max_book - i] + cumsum_b[i]:
                max_book += 1
                break
        else:
            continue
    else:
        break

print(max_book - 1)

### FIXED CODE ###

import numpy as np

N, M, K = list(map(int, input().split()))
A = list(map(int, [0] + input().split()))
B = list(map(int, [0] + input().split()))
cost = 0
cumsum_a = np.cumsum(A)
cumsum_b = np.cumsum(B)

num_book = 0
max_a = 0
ind_b = 0
max_b = 0
for i in range(1, N + 1):
    if cumsum_a[i] <= K:
        max_a = i
    else:
        break

for i in range(1, M + 1):
    if cumsum_b[i] <= K:
        max_b = i
    else:
        break

for i in range(max_a, -1, -1):
    for j in range(ind_b, max_b+1):
        if cumsum_b[j] + cumsum_a[i] <= K:
            # print("ok")
            num_book = max(i + j, num_book)
            ind_b = j
        else:
            break
print(num_book)
import numpy as np

n, W = map(int, input().split())
value = np.empty(110, dtype = 'int8')
weight = np.empty(110, dtype = 'int8')

dp = np.empty((110,10010), dtype = 'int8')

for el in range(n):
    value[el], weight[el] = map(int, input().split())

for w in range(W):
    dp[0][w] = 0

for i in range(n):
    for w in range(W + 1):
        if w >= weight[i]:
            #dp[i + 1][w]はi番目の品物の中から重さがwを超えないように選んだ時の、価値の総和の最大値
            dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i] , dp[i][w])
            #その品物を選ぶか選ばないか判定する前のその重さの時の価値の最大値が既に分かっているので、判定するものの重量を差し引いた時の価値の最大値と判定しているものの価値を足し合わせて、
            #判定する前のその時点(w)での元からある価値の最大値（dp[i][w]と比べている
            #DP表には価値の最大値が書いてあり、組み合わせを記述するわけではない
        else:
            dp[i + 1][w] = dp[i][w]

print(dp[n][W])



### FIXED CODE ###

n, W = map(int, input().split())
#item =[]
# for i in range[n]:
#     item = list(map(int, input().split()))
value =[]
weight = []
dp = [[0 for i in range(W + 1)]for j in range(n + 1)]

for el in range(n):
    x, y = map(int, input().split())
    value.append(x)
    weight.append(y)

for w in range(W):
    dp[0][w] = 0

for i in range(n):
    for w in range(W + 1):
        if w >= weight[i]:
            #dp[i + 1][w]はi番目の品物の中から重さがwを超えないように選んだ時の、価値の総和の最大値
            dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i] , dp[i][w])
            #その品物を選ぶか選ばないか判定する前のその重さの時の価値の最大値が既に分かっているので、判定するものの重量を差し引いた時の価値の最大値と判定しているものの価値を足し合わせて、
            #判定する前のその時点(w)での元からある価値の最大値（dp[i][w]と比べている
            #DP表には価値の最大値が書いてあり、組み合わせを記述するわけではない
        else:
            dp[i + 1][w] = dp[i][w]

print(dp[n][W])
N=int(input())
a=[0]*N
b=[0]*N
c=[0]*N

for i in range(N):
	a[i],b[i],c[i]=map(int,input().split())

dp=[[0 for j in range(3)] for k in range(N)]

for l in range(N):
	if l==0:
		dp[0][l]=a[l]
		dp[1][l]=b[l]
		dp[2][l]=c[l]
	else:
		dp[0][l]=max(dp[1][l-1],dp[2][l-1])+a[l]
		dp[1][l]=max(dp[0][l-1],dp[2][l-1])+b[l]
		dp[2][l]=max(dp[0][l-1],dp[1][l-1])+c[l]

print(max(dp[0][N-1],dp[1][N-1],dp[2][N-1]))

### FIXED CODE ###

N=int(input())
a=[0]*N
b=[0]*N
c=[0]*N

for i in range(N):
	a[i],b[i],c[i]=map(int,input().split())

dp=[[0 for j in range(N)] for k in range(3)]

for l in range(N):
	if l==0:
		dp[0][l]=a[l]
		dp[1][l]=b[l]
		dp[2][l]=c[l]
	else:
		dp[0][l]=max(dp[1][l-1],dp[2][l-1])+a[l]
		dp[1][l]=max(dp[0][l-1],dp[2][l-1])+b[l]
		dp[2][l]=max(dp[0][l-1],dp[1][l-1])+c[l]

print(max(dp[0][N-1],dp[1][N-1],dp[2][N-1]))
N, M = map(int, input().split())
PS = [[x for x in input().split()] for _ in range(M)]
tmp = [0] * N
ac = wa = 0

for P, S in PS:
    if S=='WA':
        tmp[int(P)] += 1
    elif S=='AC' and tmp[int(P)]!=-1:
        ac+=1
        wa+=tmp[int(P)]
        tmp[int(P)] = -1
        
print(ac,wa)

### FIXED CODE ###

N, M = map(int, input().split())
PS = [[x for x in input().split()] for _ in range(M)]
tmp = [0] * (10**5+1)
ac = wa = 0

for P, S in PS:
    if tmp[int(P)]==-1:
        continue
    if S=='WA':
        tmp[int(P)] += 1
    elif S=='AC':
        ac+=1
        wa+=tmp[int(P)]
        tmp[int(P)] = -1
        
print(ac,wa)
n = int(input())
given_a = list(map(int, input().split()))

money = 1000
kabu = 0

a = []
for kabuka in given_a:
    if len(a) > 0 and a[-1] == kabuka:
        continue
    else:
        a.append(kabuka)

n = len(a)
for i in range(n):
    if i == 0:
        if a[i+1] < a[i]:
            continue
        else:
            kabu += money // a[i]
            money %= a[i]
    elif i == n-1:
        money += kabu * a[i]
        kabu = 0
    else:
        if a[i-1] < a[i] and a[i] > a[i+1]:
            money += kabu * a[i]
            kabu = 0
        if a[i-1] > a[i] and a[i] < a[i+1]:
            kabu += money // a[i]
            money %= a[i]

print(money)




### FIXED CODE ###

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

money = 1000
kabu = 0

a = []
for kabuka in given_a:
    if len(a) > 0 and a[-1] == kabuka:
        continue
    else:
        a.append(kabuka)

n = len(a)
if n == 1:
    print(money)
    exit()


for i in range(n):
    if i == 0:
        if a[i+1] < a[i]:
            continue
        else:
            kabu += money // a[i]
            money %= a[i]
    elif i == n-1:
        money += kabu * a[i]
        kabu = 0
    else:
        if a[i-1] < a[i] and a[i] > a[i+1]:
            money += kabu * a[i]
            kabu = 0
        if a[i-1] > a[i] and a[i] < a[i+1]:
            kabu += money // a[i]
            money %= a[i]

print(money)
while True:
        (a, op, b) = input().split()
        a = int(a)
        b = int(b)

        if op = '?':
              break
        elif op = '+':
              print()
        elif op = '-':
              print()
        elif op = '*':
              print()
        elif op = '/':
              print()

### FIXED CODE ###

while True:
    (a, op, b) = input().split()
    a = int(a)
    b = int(b)

    if op == '?':
        break
    elif op == '+':
        print(a + b)
    elif op == '-':
        print(a - b)
    elif op == '*':
        print(a * b)
    elif op == '/':
        print(a // b)
import math
n, X = map(int, input().split())
x = list(map(int, input().split()))
ans = abs(x[0]-X)
for el in x[1:]:
    ans = math.gcd(ans, abs(el - X))
print(ans)


### FIXED CODE ###

from fractions import gcd

N, X = map(int, input().split())
x = list(map(int, input().split()))
z = list(map(lambda i: abs(X - i), x))
ans = z[0]
for i in range(1, N):
	ans = gcd(ans, z[i])
print(ans)
N = int(input())
p = list(map(int, input().split()))

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

print(ans)

### FIXED CODE ###

N = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(N):
    if i != N-1:
        if p[i] == i+1:
            p[i], p[i+1] = p[i+1], p[i]
            ans += 1
    else:
        if p[i] == i+1:
            p[i], p[i-1] = p[i-1], p[i]
            ans += 1

print(ans)
from sys import stdin
import math
import bisect
import heapq
import numpy as np
from math import factorial

inf = 10**3
n,m = [int(x) for x in stdin.readline().rstrip().split()]

li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
nu = []

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    #k：中継
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
point = 0
for i in range(m):
    d = [[inf for i in range(n)]for j in range(n)]
    lin = li[:i]+li[i+1:]
    for j in range(m-1):
        d[lin[j][0]-1][lin[j][1]-1] = 1
        d[lin[j][1]-1][lin[j][0]-1] = 1
    for k in range(n):
        d[k][k] = 0
    lis = warshall_floyd(d)
    for i in lis:
        if inf in i:
            point += 1
            break
print(point)

### FIXED CODE ###

from sys import stdin

inf = 10**3
n,m = [int(x) for x in stdin.readline().rstrip().split()]

li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
nu = []

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    #k：中継
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
point = 0
for i in range(m):
    d = [[inf for i in range(n)]for j in range(n)]
    lin = li[:i]+li[i+1:]
    for j in range(m-1):
        d[lin[j][0]-1][lin[j][1]-1] = 1
        d[lin[j][1]-1][lin[j][0]-1] = 1
    for k in range(n):
        d[k][k] = 0
    lis = warshall_floyd(d)
    for i in lis:
        if inf in i:
            point += 1
            break
print(point)
s=input()
n=len(s)
def mod10(x):
    p=x//10000
    q=x%10000
    if p==0:
        return (10**q)%2019
    return (mod10(q)+mod10(p))%2019


def T(i):
    if i==n-1:
        return int(s[n-1])
    return T(i+1)+10**(n-1-i)*int(s[i])
dict={}
def modi(i,dict):
    if i in dict.keys():
        return dict[i]
    else:
        if i==n-1:
            dict[i]=int(s[i])
            return int(s[i])
        else:
           # c=modi(i+1,dict)+(10**(n-1-i)*int(s[i]))
            c=c=modi(i+1,dict)+(mod10(n-1-i)*int(s[i]))
            c=c%2019
            dict[i]=c
            return c

modnum={}
for i in range(n):
    #print(T(i))
    x=modi(i,dict)
    #print(T(i),x)
    if x not in modnum.keys():
        modnum[x]=1
    else:
        modnum[x]+=1
sum=0
for md in modnum.keys():
    a=modnum[md]
    if md==0:
        sum+=a
   # print(a*(a-1)//2)
    sum+=a*(a-1)//2
print(sum)


### FIXED CODE ###

import sys
import collections as coun
sys.setrecursionlimit(10000000)
s=input()
n=len(s)
def mod10(x):
    return (10**(x%224))%2019
dp=[-1]*n
tmp=0
for i in reversed(range(n)):
    if i==n-1:
        dp[i]=int(s[i])
    else:
        dp[i]=(dp[i+1]+int(s[i])*pow(10,n-1-i,2019))%2019

#print(dp)
p=-1
for i in range(len(dp)-1):
    if dp[i]==dp[i+1]:
        dp[i]=p
        p=p-1

#print(dp)

c=coun.Counter(dp)
sum=0
for v in c.values():
    sum+=v*(v-1)//2
#print(sum)
for i in dp:
    if i==0:
        sum+=1
#print(sum)
if dp[-1]==0:
    sum=sum-1
print(sum)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
  unsigned int b;
  char step;
} Board;

int qlen=32202;

typedef enum { U, D, L, R } Direction;

typedef struct {
  int pos;
  Direction dir;
} Motion;

const Motion motion[9][5] =
  {{{1,L},{3,U},{-1}}, {{0,R},{2,L},{4,U},{-1}}, {{1,R},{5,U},{-1}},
   {{0,D},{4,L},{6,U},{-1}}, {{1,D},{5,L},{7,U},{3,R},{-1}},
   {{2,D},{8,U},{4,R},{-1}},
   {{3,D},{7,L},{-1}}, {{4,D},{8,L},{6,R},{-1}}, {{5,D},{7,R},{-1}} };

int findzero(unsigned int b)
{
  for (int i=0; i<9; i++) {
    if (b%10==0) return 8-i;
    b/=10;
  }
  return -1;
}

unsigned int sq[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,1000000000 };

#define HISTLEN 8765432

int main()
{
  int i, j, k;
  int qhead, qtail;
  qhead = qtail = 0;
  Board board;
  fscanf(stdin, "%d %d %d\n", &i, &j, &k);
  board.b = i*sq[8]+j*sq[7]+k*sq[6];
  fscanf(stdin, "%d %d %d\n", &i, &j, &k);
  board.b += i*sq[5]+j*sq[4]+k*sq[3];
  fscanf(stdin, "%d %d %d\n", &i, &j, &k);
  board.b += i*100+j*10+k;
  short int *used = (short int*)malloc(sizeof(short int)*HISTLEN);
  for (i=0; i<HISTLEN; i++) used[i]=0;
  Board *Q = (Board*)malloc(sizeof(Board)*qlen);
  board.step=0;
  Q[qhead++] = board;
  
  while (qhead>qtail) {
    board = Q[qtail++ %qlen];
    if (board.b==123456780)   break;
    
    int space = findzero(board.b);
    for (i=0; motion[space][i].pos>=0; i++) {
      Board b = board;
      Motion m = motion[space][i];
      if (m.pos==0 && b.b/sq[8]==1) continue;
      if ((m.pos==1||m.pos==2) && b.b/sq[8]==1&&(b.b%sq[8])/sq[7]==2&&(b.b%sq[7])/sq[6]==3) continue;
      int nn=b.b%sq[8-m.pos+1]/sq[8-m.pos];
      b.b = nn*sq[8-space]+b.b-nn*sq[8-m.pos];
      b.step = board.step+1;
      k=b.b/100;
      if ((used[k] & (1<<(b.b%10)))==(1<<(b.b%10))) continue;
      used[k] |= (1<<(board.b%10));
      Q[qhead++ %qlen] = b;
    }
  }
  printf("%d\n", board.step);
  return 0;
}



### FIXED CODE ###

import sys
import queue

N = 3

f = ''.join(sys.stdin.readline().split())
f += ''.join(sys.stdin.readline().split())
f += ''.join(sys.stdin.readline().split())

dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

Q = [[f,f.index('0'),0]]
V = { f: True }

while len(Q)>0:
    u = Q.pop(0)
    if u[0] == '123456780':  break
    sx, sy = u[1]//N, u[1]%N
    for dx, dy in dd:
        tx, ty = sx+dx, sy+dy
        if tx<0 or ty<0 or tx>=N or ty>=N: continue
        v = u[:]
        n1, n2 = u[1], tx*N+ty
        v[1] = n2
        if n1>n2: n1, n2 = n2, n1
        v[0] = v[0][0:n1]+v[0][n2]+v[0][n1+1:n2]+v[0][n1]+v[0][n2+1:]
        if not V.get(v[0], False):
            V[v[0]] = True
            v[2] += 1 # dir[r]                                                       
            Q.append(v)

print(u[2])