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

import functools
import fractions

N = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(N):
	a_new = a[0:i]+a[i+1:N]
	gcd = functools.reduce(fractions.gcd,a_new)
	ans = max(ans,gcd)

print(ans)


### FIXED CODE ###

import functools
import fractions


N = int(input())
a = list(map(int,input().split()))
ans = 1
gcd = functools.reduce(fractions.gcd,a)
s_front = [1]*N
s_back = [1]*N
s_front[0] = a[0]
s_back[0] = a[N-1]

for i in range(N):
	if i > 0:
		s_front[i] = fractions.gcd(s_front[i-1],a[i])
		s_back[i] = fractions.gcd(s_back[i-1],a[N-i-1])
for i in range(N):
	if i == 0:
		gcd_new = s_back[N-2]
	elif i == N-1:
		gcd_new = s_front[N-2]
	else:
		gcd_new = fractions.gcd(s_front[i-1],s_back[N-i-2])
	ans = max(ans,gcd_new)
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(hoge) for hoge in input().split()]
A.sort()
dp = [False] * (max(A) + 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (max(A) // a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(hoge) for hoge in input().split()]
A.sort()
M = max(A)
dp = [False] * (M+ 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (M// a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)
### BUGGY CODE ###

def main():

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort(reverse = True)
    F.sort()

    if K >= sum(A): return 0

    B = [[A[i] * F[i], A[i], F[i]] for i in range(N)]
    l, r = 0, max([A[i]*F[i] for i in range(N)])
    # ans = float('inf')
    while l < r:
        m = (l+r) // 2
        count = 0
        for i in range(N):
            if B[i][0] - m > 0:
                if (B[i][0] - m) % B[i][2] == 0:
                    count += (B[i][0] - m) // B[i][2]
                else:
                    count += (B[i][0] - m) // B[i][2] + 1
        if count <= K:
            if r == m: break
            r = m
        else:
            # ans = min(ans, m)
            if l == m: break
            l = m
        # print(l, r)
    return r



if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def main():
 
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort(reverse = True)
    F.sort()
 
    if K >= sum(A): return 0
 
    B = [A[i] * F[i] for i in range(N)]
    l, r = 0, max(B)
    ans = float('inf')
    while l <= r:
        m = (l+r) // 2
        count = 0
        for i in range(N):
            if B[i] - m > 0:
                count += (B[i] - m) // F[i]
                if (B[i] - m) % F[i] != 0:
                    count += 1
        if count <= K:
            ans = min(ans, m)
            if r == m-1: break
            r = m-1
        else:
            if l == m+1: break
            l = m+1
        # print(l, r)
    return ans
 
if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

N = int(input())
A = [0]*N
for i in range(N):
    A[i] = int(input())

for j in range(N):
    B = A[0:j]
    C = A[j+1:N]
    D = B+C
    print(max(D))

### FIXED CODE ###

N = int(input())
A = [0]*N
for i in range(N):
    A[i] = int(input())

mx = max(A)
mxidx = A.index(mx)

for i in range(N):
    if i == mxidx:
        B = A[0:i] + A[i+1:N]
        print(max(B))
    else:
        print(mx)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
A.sort()
ans=1
if N%2==1:
  i=1
  if A[0]!=0:
    print(0)
    exit()
  while i<N:
    if A[i]==A[i+1] and A[i]==(i//2+1)*2:
      i+=2
    else:
      print(0)
      exit()
  for i in range(N//2):
    ans*=2
    ans%=mod
  print(ans)
else:
  i=0
  while i<N:
    if A[i]==A[i+1] and A[i]==(i//2)*2+1:
      i+=2
    else:
      print(0)
  for i in range(N//2):
    ans*=2
    ans%=mod
  print(ans)

### FIXED CODE ###

def main():
  N=int(input())
  A=list(map(int,input().split()))
  mod=10**9+7
  ans=1
  A.sort()
  if N%2==0:
    for i in range(0,N,2):
      if A[i]!=A[i+1] or A[i]!=i+1:
        print(0)
        exit()
      ans=ans*2%mod
    print(ans)
  else:
    if A[0]!=0:
      print(0)
      exit()
    ans=1
    for i in range(1,N,2):
      if A[i]!=A[i+1] or A[i]!=i+1:
        print(0)
        exit()
      ans=ans*2%mod
    print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

l, r = map(int, input().split())
if (r-l) >= 2019:
    print(0)
ans = 2019
for i in range(l, r+1):
    for j in range(i+1, r+1):
        ans = min(ans, (i*j)%2019)
print(ans)

### FIXED CODE ###

l, r = map(int, input().split())
if (r-l) >= 2019:
    print(0)
    exit()
ans = 2019
for i in range(l, r+1):
    for j in range(i+1, r+1):
        ans = min(ans, (i*j)%2019)
print(ans)
### BUGGY CODE ###

l, r = list(map(int,input().split()))
Set = set([l%2019])
for i in range(r-l):
	Set.add((l+1+i)%2019)
List = list(Set)
answer = (l * r) % 2019
for i in range(len(List)):
	for j in range(len(List)):
		if(i < j):
			if(answer > (List[i] * List[j])% 2019):
				answer = (List[i] * List[j])% 2019
print(answer)

### FIXED CODE ###

l, r = list(map(int,input().split()))
lmod = l % 2019
rmod = r % 2019
if(r-l) >= 2018:
	answer = 0
elif(lmod > rmod):
	answer = 0
else:
	answer = (rmod * lmod)% 2019
	for i in range(rmod - lmod + 1):
		for j in range(rmod - lmod + 1):
			if(i < j):
				if(answer > (lmod + i) * (lmod + j) % 2019):
					answer = (lmod + i) * (lmod + j) % 2019
print(answer)
### BUGGY CODE ###

import math
S = list(input())

N = len(S)
flag = 0
x = 0
y = 0
X = []
Y = [-2]
for n in range(N):
    if flag==0 and S[n]=='R':
        pass
    elif flag==0 and S[n]=='L':
        flag = 1
        Y.append(n-1)
    elif flag==1 and S[n]=='L':
        pass
    else:
        flag = 0
        X.append([x,n-1])
        x = n
X.append([x,N-1])

ans = []
K = len(Y)-1
for k in range(K):
    ans = ans + [0]*(Y[k+1]-Y[k]-2)
    ans = ans + [math.ceil((Y[k+1]-X[k][0]+1)/2) + math.floor((X[k][1]-Y[k+1])/2)]
    ans = ans + [math.floor((Y[k+1]-X[k][0]+1)/2) + math.ceil((X[k][1]-Y[k+1])/2)]
ans = ans + [0]*(N-Y[K]-2)

print(*ans)

### FIXED CODE ###

from collections import deque 
import math
S = list(input())

N = len(S)
flag = 0
x = 0
y = 0
X = []
Y = [-2]
for n in range(N):
    if flag==0 and S[n]=='R':
        pass
    elif flag==0 and S[n]=='L':
        flag = 1
        Y.append(n-1)
    elif flag==1 and S[n]=='L':
        pass
    else:
        flag = 0
        X.append([x,n-1])
        x = n
X.append([x,N-1])

ans = []
ans = deque(ans)
K = len(Y)-1
for k in range(K):
    ans += [0]*(Y[k+1]-Y[k]-2)
    ans.append(math.ceil((Y[k+1]-X[k][0]+1)/2) + math.floor((X[k][1]-Y[k+1])/2))
    ans.append(math.floor((Y[k+1]-X[k][0]+1)/2) + math.ceil((X[k][1]-Y[k+1])/2))
ans += [0]*(N-Y[K]-2)

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

def main():
    N = int(input())
    a = list(map(int, input().split()))
    #N = 1000
    #a = [i for i in range(N)]

    #summation = [abs(sum(a[:(i+1)]) - sum(a[(i+1):])) for i in range(len(a)-1)]

    summation = []
    sumtemp = sum(a)
    for i in range(len(a)-1):
        tmp1 = sum(a[:(i+1)])
        tmp2 = sumtemp - tmp1
        tmp = abs(tmp1 - tmp2)
        summation.append(tmp)
        
    print(min(summation))

main()



### FIXED CODE ###

def main():
    N = int(input())
    a = list(map(int, input().split()))
    #N = 1000
    #a = [i for i in range(N)]

    #summation = [abs(sum(a[:(i+1)]) - sum(a[(i+1):])) for i in range(len(a)-1)]

    summation = []
    sumtemp = sum(a)
    tmp1 = 0
    for i in range(len(a)-1):
        tmp1 += a[i]
        tmp2 = sumtemp - tmp1
        tmp = abs(tmp1 - tmp2)
        summation.append(tmp)
        
    print(min(summation))

main()
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
for i in range(Q):
    s,e = map(int, input().split())
    print(S[s-1:e].count("AC"))


### FIXED CODE ###

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


cnt = [0] * (N)

for i in range(1, N):
	if S[i-1:i+1] == "AC":
		cnt[i] = cnt[i-1] + 1
	else:
		cnt[i] = cnt[i-1]

for _ in range(Q):
	l, r = map(int, input().split())
	print(cnt[r-1] - cnt[l-1])
### BUGGY CODE ###

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

N = int(input())

A = list(map(int,input().split()))
A.sort()

mod = 10**9 + 7

s = [2]
now = 3
dic = {}

while now ** 2 <= 10 ** 6:

    flag = True
    for i in s:
        if now % i == 0:
            flag = False
            break

    if flag:
        s.append(now)
    now += 2

for i in s:
    dic[i] = 0

for i in range(N):
    if i > 0 and A[i] == A[i-1]:
        continue
    a = A[i]

    for j in s:
        cnt = 0
        while a % j == 0:
            cnt += 1
            a //= j

        dic[j] = max(dic[j],cnt)

    if a != 1:
        s.append(a)
        dic[a] = 1

lcm = 1

for i in s:
    for j in range(dic[i]):
        lcm *= i

ans = 0
for i in range(N):
    ans += lcm // A[i]
    ans %= mod
print (ans)

### FIXED CODE ###

import fractions

def lcm(x,y):
  return x // fractions.gcd(x,y) * y


mod = 10**9+7


N = int(input())

A = list(map(int,input().split()))

B = 0
for i in A:
    B += pow(i,mod-2,mod)
    B %= mod

g = 1

for i in range(N):
    g = lcm(g,A[i])

print (g * B % mod)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(N):
  ans *= a[i]
if(ans>10**18):
    ans = -1
print(ans)


### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
ans = 1
if(0 in a):
  ans = 0
else:
  for i in range(N):
    ans*=a[i]
    if(ans>10**18):
      ans = -1
      break
print(ans)
### BUGGY CODE ###

import math

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

M = max(A)
ans = 1

for i in reversed(range(2, M+1)):
  l = 0
  for j in range(N):
    if A[j] % i > 0:
      l += 1
  
  if l <= 1:
    ans = i
    break

print(ans)

### FIXED CODE ###


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


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

if N == 2:
  print(max(A))
else:

  L = [0 for j in range(N+1)]
  R = [0 for j in range(N+1)]
  
  for j in range(N):
    L[j+1] = gcd(L[j], A[j])
  for j in reversed(range(N)):
    R[j] = gcd(R[j+1], A[j])

    m = -1
  for j in range(N):
    m = max(m, gcd(L[j], R[j+1]))
  print(m)
### BUGGY CODE ###

from bisect import*
class BTreeNode:
    def __init__(self):self.key,self.child=[],[]
def main():
    root=BTreeNode()
    def search_higher(key):
        ptr=root
        ret=None
        while ptr.child:
            i=bisect(ptr.key,key)
            if i!=len(ptr.key):ret=ptr.key[i]
            ptr=ptr.child[i]
        i=bisect(ptr.key,key)
        if i!=len(ptr.key):ret=ptr.key[i]
        return ret
    def search_lower(key):
        ptr=root
        ret=None
        while ptr.child:
            i=bisect_left(ptr.key,key)
            if i:ret=ptr.key[i-1]
            ptr=ptr.child[i]
        i=bisect_left(ptr.key,key)
        if i:ret=ptr.key[i-1]
        return ret
    def insert_rec(ptr,key):
        b_size=512
        if not ptr.child:
            insort(ptr.key,key)
            if len(ptr.key)==b_size*2-1:
                ret=BTreeNode()
                ret.key=ptr.key[:b_size]
                ptr.key=ptr.key[b_size:]
                return ret
        else:
            i=bisect(ptr.key,key)
            tmp=insert_rec(ptr.child[i],key)
            if tmp:
                ptr.key.insert(i,tmp.key.pop())
                ptr.child.insert(i,tmp)
                if len(ptr.child)==b_size*2:
                    ret=BTreeNode()
                    ret.child=ptr.child[:b_size]
                    ptr.child=ptr.child[b_size:]
                    ret.key=ptr.key[:b_size]
                    ptr.key=ptr.key[b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root.key,root.child=[tmp.key.pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

n,k = map(int, input().split())
p = [int(x) for x in input().split()]

max = -1
ans=0

for i in range(0,n-k+2):
    buf = p[i:i+k]
    tmp = sum(buf)
    if tmp > max:
        ans=0
        max = tmp
        for j in range(len(buf)):
            s_buf = 0
            for l in range(1,buf[j]+1):
                s_buf+=l
            ans += s_buf/buf[j]
            s_buf=0

print(ans)


### FIXED CODE ###

n,k = map(int, input().split())
p = [int(x) for x in input().split()]

li = []
count=0
ans = 0

for i in range(len(p)):
    p[i] += 1
    li.append(p[i])
    if len(li) < k:
        continue
    elif len(li) == k:
        max = sum(li)
        buf = max
    elif len(li) > k:
        tmp = buf - li[count] + li[-1]
        buf = tmp
        if tmp >= max:
            max = tmp
        count+=1

print(max/2)
### BUGGY CODE ###

n=int(input())
l=[int(i) for i in input().split()]
l.sort()
ans=0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if l[i]+l[j]>l[k]:
        ans+=1
      else:
        break
print(ans)
      
        
        

### FIXED CODE ###

n=int(input())
l=[int(i) for i in input().split()]
l.sort()
ans=0
ans1=0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+ans1,n):
      ans1=0
      if l[i]+l[j]>l[-1]:
        ans+=n-j-1
        break
      elif l[i]+l[j]<=l[k] :
        ans+=k-j-1
        ans1+=k-j-1
        break
      
      
print(ans)
### BUGGY CODE ###

s = input()
number = 0
for i in range(0,len(s)- 3):
    sum = 100 * int(s[i]) + 10 * int(s[i+1]) + int(s[i+2])
    for j in range(i+3,len(s)):
        sum = sum*10  + int(s[j])
        #print(sum)
        if sum % 2019 == 0:
            
            number = number + 1
    
print(number)

### FIXED CODE ###

s = input()
t = 0
number = 0
#m = [0 for i in range(2019)]
m = [0]*2019
m[0] = 1
a = 1
for i in range(len(s)):
    t = t  +  int(s[len(s) - 1 - i])* a 
    #print(t)
    m[t % 2019] += 1
    a = a * 10
    a = a % 2019
    #print(t%2019)

for j in range(2019):
    #if m[j]>= 2:
    number += (m[j]*(m[j] - 1))//2

print(number)
### BUGGY CODE ###

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

for i in range(1, n):
    print(a.index(i) + 1, end=" ")

print(a.index(n) + 1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
newa = [0] * n

for i in range(n):
    newa[a[i] - 1] = i + 1

print(*newa, sep=" ")
### BUGGY CODE ###

K, S = map(int, input().split())
cnt = 0
for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i+j+k == S:
        cnt += 1
print(cnt)

### FIXED CODE ###

K, S = map(int, input().split())
cnt = 0
for i in range(K+1):
  for j in range(K+1):
    k = S - i -j
    if 0 <= k and k <= K:
      cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range (N):
  for j in range (i+1,N):
    if A[i]==A[j]:
      print('NO')
      exit()
      
print('YES')
 



### FIXED CODE ###

N =int(input())
A =list(map(int ,input().split()))
s =set(A)
if len(A) >len(s):
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

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

while True:
	# 割引券，駅，路線，スタート，ゴール
	c, n, m, s, d = map(int, raw_input().split())
	if not (c or n or m or s or d): break
	field = {}
	for i in xrange(m):
		a, b, f = map(int, raw_input().split())
		field[(a, b)] = f;
		field[(b, a)] = f;
	visited = set()
	q = []
	heapq.heappush(q, (0, c, -1, s))
	while q:
		cost, rem, frm, pos = heapq.heappop(q)
		if pos == d and (rem == 0 or (c > n and rem == c - n)):
			print cost
			break
		visited.add((rem, pos))
		for i in xrange(1, n + 1):
			edge = (pos, i)
			if edge in field:
				next = (rem, i)
				if not next in visited:
					heapq.heappush(q, (cost + field[edge], rem, pos, i))
				if rem > 0:
					next = (rem - 1, pos)
					if not next in visited:
						heapq.heappush(q, (cost + field[edge] / 2, rem - 1, pos, i))

### FIXED CODE ###

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

while True:
	# 割引券，駅，路線，スタート，ゴール
	c, n, m, s, d = map(int, raw_input().split())
	if not (c or n or m or s or d): break
	field = {}
	for i in xrange(m):
		a, b, f = map(int, raw_input().split())
		field[(a, b)] = field[(b, a)] = f;
	visited = {}
	q = []
	heapq.heappush(q, (0, c, s))
	while q:
		cost, rem, pos = heapq.heappop(q)
		if pos == d:
			print cost
			break
		for i in xrange(1, n + 1):
			edge = (pos, i)
			next = (rem, i)
			ncost = cost + field.get(edge, 0x7fffffff)
			if ncost < visited.get(next, 0x7fffffff):
				heapq.heappush(q, (ncost, rem, i))
				visited[next] = ncost
			next = (rem - 1, i)
			ncost = cost + field.get(edge, 0x7fffffff) / 2
			if rem > 0 and ncost < visited.get(next, 0x7fffffff):
				heapq.heappush(q, (ncost, rem - 1, i))
				visited[next] = ncost
### BUGGY CODE ###

# E
import numpy as np

N = int(input())
a_list = [0]*(N+1)
for i in range(N+1):
    a_list[N-i] = int(input())

# a0を割り切る素数を全部求める
p_list = []
## 10^5までの素数を計算
primes = np.arange(10**5)
primes[:2] = 0
for p in range(2, 10**5):
    if primes[p]:
        primes[2*p::p] = 0
primes = primes[primes>0]

## 素因数分解
A = a_list[0]
for p in primes:
    if A % p == 0:
        p_list.append(p)
    while A % p == 0:
        A = A // p
if A > 1:
    p_list.append(A)

# 個別に条件確認
res_list = []
check_list = np.zeros(N+1, dtype="int")
for p in p_list:
    r = 0
    check_list = check_list*0
    for i in range(min(p, N+1)):
        check_list[i] = a_list[i]
    for i in range(p, N+1):
        check_list[(i-1) % (p-1) + 1] += a_list[i]
    for i in range(N+1):
        r += check_list[i] % p
    if r == 0:
        res_list.append(p)
        
for p in res_list:
    print(p)

### FIXED CODE ###

# E

# 入力
# input
N = int(input())
a_list = [0]*(N+1)
for i in range(N+1):
    a_list[N-i] = int(input())


# 10^5までの素数を計算
# list primes <= 10^5 
primes = list(range(10**5))
primes[0] = 0
primes[1] = 0
for p in range(2, 10**5):
    if primes[p]:
        for i in range(2*p, 10**5, p):
            primes[i] = 0
primes = [p for p in primes if p>0]
# primes <= N
p_list_small = [p for p in primes if p <= N]


# A_Nを素因数分解、Nより大きい素因数をp_list_largeに追加
# A_N, ..., A_0の最大公約数の素因数でやっても同じ
# list prime factors of A_N, if greater then N, add to p_list_large
# you can use prime factors of gcd(A_N, ..., A_0) instead 

p_list_large = []
A = abs(a_list[-1])
for p in primes:
    if A % p == 0:
        if p > N:
            p_list_large.append(p)
        while A % p == 0:
            A = A // p
if A != 1:
    p_list_large.append(A)

# 個別に条件確認
# check all p in p_list_small
# x^p ~ x (mod p)
res_list = []
for p in p_list_small:
    r = 0
    check_list = [0]*(N+1)
    for i in range(p):
        check_list[i] = a_list[i]
    for i in range(p, N+1):
        check_list[(i-1) % (p-1) + 1] += a_list[i]
    for i in range(p):
        if check_list[i] % p != 0:
            r = 1
    if r == 0:
        res_list.append(p)
        
# 個別に条件確認
# check all p in p_list_large
# a_i % p == 0
for p in p_list_large:
    r = 0
    for i in range(N+1):
        if a_list[i] % p != 0:
            r = 1
    if r == 0:
        res_list.append(p)
        
for p in res_list:
    print(p)
### BUGGY CODE ###

baisu=set([])


n=input()
cnt=0
for i in range(len(n)-4):
    for j in range(i+5,len(n)+1):
        if int(n[i:j])%2019==0:
            cnt+=1

print(cnt)



### FIXED CODE ###

s=input()



"""
◆エッセンス1：割り切れるとは、二つに分けた数字のmodが一緒
例)
1817181712114の
18171が2019で割り切れるかどうかを判断する。

18171は(181712114-2114)/10000となるので、
181712114mod2019＝2114mod2019の時、2019で割り切れる。

1817181712114mod2019
 817181712114mod2019
  17181712114mod2019
   7181712114mod2019
    181712114mod2019
     81712114mod2019
      1712114mod2019
       712114mod2019
    　　・・・・
とmodを調べていき、値が同じペアは割り切れる。
"""

"""
◆エッセンス2：大きい数字は都度modを取る

これだけでもループは1回になるんだけど、
|S|が長すぎてTLEとなってしまう（|S|は10**5）
1234567 mod 2019
=(1*10**7)mod2019 + (234567mod2019)
=(1*10mod2019 * 10**6mod2019)+ (234567mod2019)

10**nを毎回modを取ることで、計算する数字の長さを短くする。

"""



#modの値を保持する配列
cnt=[0]*2019
#mod2019 =0 は、それ一つで割り切れるので。引き算をする必要が無い。
cnt[0]=1

#10の倍数を保持する
fac=1
ss=0
for i in range(len(s)):
    #後ろの数字から順番にとってくる
    ss += int(s[len(s)-i-1])*fac
    ss%=2019
    fac=fac*10
    fac%=2019
    cnt[ss]+=1
    

result=0
for c in cnt:
    result+=c*(c-1)//2

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

import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def S(): return input().rstrip()
def LIR(n): return [S().split() for i in range(n)]

def main():
    s = S()
    Q = I()
    Qu = LIR(Q)
    mode = 0
    for que in Qu:
        if que[0] == '1':
            mode += 1
        else:
            if mode%2:
                if que[1] == '1': s = ''.join([s, que[2]])
                else: s = ''.join([que[2], s])
            else:
                if que[1] == '1': s = ''.join([que[2], s])
                else: s = ''.join([s, que[2]])
    if mode%2: print(s[::-1])
    else: print(s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def S(): return input().rstrip()
def LIR(n): return [S().split() for i in range(n)]

def main():
    s = S(); Q = I()
    mode = 2
    d = deque(s)

    for i in range(Q):
        query = S()
        if query[0] == "1": mode = 3 - mode
        else:
            t, f, c = map(str, query.split())
            if (int(f) + mode)% 2  == 0: d.append(c)
            else: d.appendleft(c)
    if mode == 2: print(''.join(d))
    else: print(''.join(list(d)[::-1]))

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

n,q=[int(i) for i in input().split()]
s=input()
for i in range(q):
    c=0
    query = (lambda x: [x[0]-1, x[1]])([int(i) for i in input().split()])
    seq = s[query[0]:query[1]]
    for i in range(query[1]-query[0]-1):
        if seq[i:i+2] == "AC":
            c += 1
    print(c)


### FIXED CODE ###

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

cumsum = [0]
for i in range(1, N):
    if (S[i-1], S[i]) == ("A", "C"):
        cumsum.append(cumsum[i-1]+1)
    else:
        cumsum.append(cumsum[i-1])

for i in range(Q):
    l, r = [int(i)-1 for i in input().split()]
    print(cumsum[r]-cumsum[l])