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

import sys

def Not_Divisible(n,p):
    k=0
    for i,a in enumerate(p):
        for j,b in enumerate(p):
            if  i != j and a % b == 0:
                k-=1
                break
        k+=1
    return k

if __name__ == '__main__':
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = list(map(int,inp2))
    print(Not_Divisible(n,p))

### FIXED CODE ###

import sys

def Not_Divisible(n,p):
    maxp = max(p)
    dp = [[True,0] for _ in range(maxp+1)]
    for a in p:
        dp[a][1]+=1
        t =2
        while a*t <= maxp:
            if dp[a*t][0] == True :
                dp[a*t][0] = False
            t+=1
    k=0
    for d in p:
        if dp[d][1] == 1 and dp[d][0] == True:
            k+=1
    return k


def main():
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = tuple(map(int,inp2))
    print(Not_Divisible(n,p))


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

n=int(input())
a_list=list(map(int, input().split()))
multi_sum=1
LIMIT=10**18
for a_i in a_list:
    multi_sum*=a_i

if multi_sum > LIMIT:
    multi_sum=-1
print(multi_sum)



### FIXED CODE ###

n=int(input())
a_list=list(map(int, input().split()))
multi_sum=1
LIMIT=1000000000000000000

if 0 not in a_list:
    for a_i in a_list:
        multi_sum*=a_i
        if multi_sum > LIMIT:
            multi_sum=-1
            break
else:
    multi_sum=0

print(multi_sum)
### BUGGY CODE ###

from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)+1, input().split()))
d = tuple(map(lambda x: int(x)+1, input().split()))
s = ['#'*(w+4)] * 2
for _ in range(h):
    s.append(f'##{input()}##')
s.extend(['#'*(w+4)] * 2)

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * (w+4) for _ in range(h+4)]
cost[c[0]][c[1]] = 0
yet = deque([(c[0], c[1], 0)])
done = deque()

while yet:
    y, x, m = yet.popleft()
    done.append((y, x, m))
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        yet.append((hh, ww, m))
    # Move B
    if not yet:
        while done:
            y, x, m = done.popleft()
            for dx, dy in move_b_area:
                hh, ww = y + dy, x + dx
                if s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
                    continue
                cost[hh][ww] = m + 1
                yet.append((hh, ww, m + 1))

print(v if (v := cost[d[0]][d[1]]) < float('inf') else -1)


### FIXED CODE ###

from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.appendleft((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < float('inf') else -1)
### BUGGY CODE ###

N = int(input())
l = []
for i in map(int,input().split()):
    l.append(i)
for j in range(1,N+1):
    print(l.count(j))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
a = [0] * N

for i in A:
    a[i-1] += 1

for j in range(N):
    print(a[j])
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return True

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = - (10 ** 18 + 10)
    r = 10 ** 9
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = -(10 ** 9)
    r = 10 ** 18 + 10
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(r)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)
### BUGGY CODE ###

n,m=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for _ in range(m)]

BC.sort(key=lambda x:(x[1],x[0]),reverse=True)
cnt=0
for b,c in BC:
  if cnt>=n: break
  for _ in range(b):
    A.append(c)
A.sort(reverse=True)
print(sum(A[:n]))

### FIXED CODE ###

n,m=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for _ in range(m)]

BC.sort(key=lambda x:(x[1],x[0]),reverse=True)
cnt=0
for b,c in BC:
  for _ in range(b):
    if cnt>=n: break
    A.append(c)
    cnt+=1
A.sort(reverse=True)
print(sum(A[:n]))
### BUGGY CODE ###

N=int(input())
# N=7
A=list(map(int,input().split()))
A=sorted(A)
B=[]
for i in range(N):
    B=[j for j in A if j-1==i]
    print(len(B))
    B=[]

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
counter=[0]*N
for i in A:
    counter[i-1]+=1
print(*counter,sep='\n')
### BUGGY CODE ###

n = int(input())
a =[int(x) for x in input().split()]
ans = 0
for index,i in enumerate(a):
    for j in a[index+1:]:
        ans = (ans + i * j) % (10**9 + 7)
print(ans)        

### FIXED CODE ###

n = int(input())
a_list =[int(x) for x in input().split()]
mod = 10**9 + 7

s_list = [0]*(n+1)
for i,a in enumerate(a_list):
    s_list[i+1] = s_list[i]+a


ans = 0
for i,a in enumerate(a_list):
    ans += a * (s_list[n]-s_list[i+1])
    
print(ans%mod)
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
score=[]
for x in range(a,b+1):
  for y in range(c,d+1):
    score.append(x*y)
print(max(score))

### FIXED CODE ###

a,b,c,d = map(int,input().split())
score=[]
score+=a*c,b*c,a*d,b*d
print(max(score))
### BUGGY CODE ###

n = int(input())
An = list(map(int, input().split()))
ans = An[0]
for i in range(1,n):
  if An[i] == 0:
    ans = 0
    break
  if An[i] > (10 ** 18):
    ans = -1
    break
  ans *= An[i]
  if ans > (10 ** 18):
    ans = -1
print(str(ans))


### FIXED CODE ###

n = int(input())
An = list(map(int, input().split()))
An.sort(reverse=True)
ans = An[0]
for i in range(1,n):
  if An[i] == 0:
    ans = 0
    break
  if An[i] > (10 ** 18):
    ans = -1
    break;
if ans > 0:
  ans = An[0]
  for i in range(1,n):
    if An[i] > (10 ** 18):
      ans = -1
      break
    ans *= An[i]
    if ans > (10 ** 18):
      ans = -1
      break

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

n=int(input())
a=list(map(int, input().split()))
sum_now=a[0]
sum_before=-a[0]
count=0
for i in range(n):
    while sum_now*sum_before>=0:
        if sum_before==0:
            sum_now=-a[1]/abs(a[1])
            count+=1
        else:
            sum_now=sum_now-sum_before/abs(sum_before)
            count+=1
    if i!=n-1:
        sum_before=sum_now
        sum_now=sum_now+a[i+1]
print(count)

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
sum_now=a[0]
sum_before=-a[0]
count_1=0
count_2=0
for i in range(n):
    if sum_now*sum_before>=0:
        if sum_before==0:
            sum_now=-a[1]/abs(a[1])
            count_1+=1
        else:
            count_1+=abs(int(sum_now))+1
            sum_now=-sum_before/abs(sum_before)
    if i!=n-1:
        sum_before=sum_now
        sum_now=sum_now+a[i+1]

sum_now=a[0]
sum_before=-a[0]
if sum_before==0:
    sum_now=a[1]/abs(a[1])
    sum_before=-sum_now
    count_2+=1
else:
    count_2+=abs(int(sum_now))+1
    sum_now=-sum_now/abs(sum_now)
    sum_before=-sum_now
for i in range(n):
    if sum_now*sum_before>=0:
        if sum_before==0:
            sum_now=a[1]/abs(a[1])
            count_2+=1
        else:
            count_2+=abs(int(sum_now))+1
            sum_now=-sum_before/abs(sum_before)
    if i!=n-1:
        sum_before=sum_now
        sum_now=sum_now+a[i+1]
print(min(count_1, count_2))
### BUGGY CODE ###

import sys

n = int(input())

a = []
for i in range(n):
  v = list(map(int, input().split(' ')))
  a.append(v)

f = True
day = 1
while(f):
  done = set()
  nokori_games = 0
  
  for m in range(n):
    nokori_games += len(a[m])
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].pop(0)
        a[teki - 1].pop(0)
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
  if not nokori_games:
    print(day)
    sys.exit()
  else:
    if not len(done):
      print(-1)
      sys.exit()
  day += 1


### FIXED CODE ###

import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()
### BUGGY CODE ###

#!/usr/bin/env python3

s = str(input())
k = int(input())
n = len(s)

sets1 = set([])
for i in range(0, len(s)):
    sets1.add(s[i])

sorted_sets1 = sorted(sets1)

for moji in sorted_sets1:
    index = []
    max_len = 0
    for i in range(len(s)):
        if s[i] == moji:
            index.append(i)
            max_len = max(max_len, n-i)

    # print(index)
    setsn = set([])
    for i in range(0, max_len):
        for index_tmp in index:
            setsn.add(s[index_tmp:index_tmp+i+1])
    # print(setsn)
    if len(setsn) >= k:
        print(sorted(setsn)[k-1])
        break
    else:
        k -= len(setsn)


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque


def search(moji):
    num = len(moji)
    setsn = set([])
    for i in range(len(s)-num+1):
        if s[i:i+num] == moji:
            str_ = s[i:i+num+1]
            if len(str_) == num+1:
                setsn.add(str_)
    sorted_setsn = sorted(setsn, reverse=True)

    return sorted_setsn


s = str(input())
k = int(input())
n = len(s)

sets1 = set([])
for i in range(0, len(s)):
    sets1.add(s[i])

sorted_sets1 = sorted(sets1)

# if k == 1:
#     print(sorted_sets1[0])
#     exit()
# else:
#     k -= 1

dq = deque(sorted_sets1)

while(len(dq)):
    # print(dq, k)
    moji = dq.popleft()
    k -= 1
    if k == 0:
        print(moji)
        exit()
    sorted_setsn = search(moji)

    # print(sorted_setsn)
    dq.extendleft(sorted_setsn)
### BUGGY CODE ###

MOD = 10**9 + 7

def mul(a, b):
    return [
        [sum(aij * bij for aij, bij in zip(ai, bi)) % MOD for bi in zip(*b)]
        for ai in a]

def pow(b, k):
    if k == 1:
        return b
    i = 0
    while 2 ** (i + 1)<= k:
        i += 1

    k -= 2 ** i
    if k > 0:
        t = pow(b, k)
    for j in range(i):
        b = mul(b, b)
    if k > 0:
        b = mul(b, t)
    return b


def main():
    N, K = (int(i) for i in input().split())
    A = []
    for i in range(N):
        A.append([int(j) for j in input().split()])
    A = [i for i in zip(*A)]
    v = [[1] * N]
    return sum(mul(v, pow(A, K))[0]) % MOD

print(main())


### FIXED CODE ###

MOD = 10**9 + 7

def mul(a, b):
    return [
        [sum(aij * bij for aij, bij in zip(ai, bi)) % MOD for bi in zip(*b)]
        for ai in a]

def pow(b, k):
    r = [[1 if i == j else 0 for i in range(len(b))] for j in range(len(b))]
    while k:
        if k & 1:
            r = mul(r, b)
        k >>= 1
        b = mul(b, b)
    return r


def main():
    N, K = (int(i) for i in input().split())
    A = []
    for i in range(N):
        A.append([int(j) for j in input().split()])
    A = [i for i in zip(*A)]
    v = [[1] * N]
    return sum(mul(v, pow(A, K))[0]) % MOD

print(main())
### BUGGY CODE ###

S = input()[::-1]
digits = 1
num, ans = 0, 0
mod_list = [0] * 2019
mod_list[0] = 1

for c in S:
  num += int(c) * digits
  mod_list[num % 2019] += 1
  digits *= 10

for i in range(2019):
  ans += mod_list[i] * (mod_list[i] - 1) // 2
  
print(ans)

### FIXED CODE ###

S = input()[::-1]
digits = 1
num, ans = 0, 0
mod_list = [0] * 2019
mod_list[0] = 1

for c in S:
  num += int(c) * digits
  mod_list[num % 2019] += 1
  digits *= 10
  digits %= 2019

for i in range(2019):
  ans += mod_list[i] * (mod_list[i] - 1) // 2
  
print(ans)
### BUGGY CODE ###

def main():
    (l, r) = list(map(int, input().split()))

    min = 2020
    for i in range(l, r + 1):
        for j in range(i + 1, r + 1):
            mod = i * j % 2019
            if mod <= min:
                min = mod

    print(min)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    (l, r) = list(map(int, input().split()))

    ans = 2020
    for i in range(l, min(r + 1, l + 2019)):
        for j in range(i + 1, min(r + 1, i + 2020)):
            mod = i * j % 2019
            if mod <= ans:
                ans = mod

    print(ans)

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

S=input()

i=0
T=""
while i<len(S):

    if i+1<len(S) and S[i]+S[i+1]=="BC":
        T+="D"
        i+=2
    else:
        T+=S[i]
        i+=1
T=list(T)
count=0
count2=-1
m=0
#print(T)
while count!=count2:

    count2=count
    flag=0
    for i in range(m,len(T)-1):
        if "A"==T[i] and "D" == T[i+1]:
            T[i]="D"
            T[i+1]="A"
            count+=1
            """if flag==0:
                m=i
                flag=1"""
        #print(T)
print(count)


### FIXED CODE ###

S=input()

i=0
T=[]
while i<len(S):

    if i+1<len(S) and S[i]+S[i+1]=="BC":
        T.append("D")
        i+=2
    else:
        T.append(S[i])
        i+=1
count=0
m=0
Acount=0
#print(T)
for i in range(len(T)):
    if "A"==T[i]:
        Acount+=1
    elif "D"==T[i]:
        count+=Acount
    else:
        Acount=0



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

N = int(input())
a = [int(x) for x in input().split()]
L = len(a)
for i in range(1,N+1):
    answer = 0
    for j in range(L):
        if i == a[j]:
            answer += 1
    print(answer)

### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]
answer = [0] * N
for i in range(1,N):
    x = a[i-1]
    answer[x-1] +=1

for i in range(N):
    print(answer[i])
### BUGGY CODE ###

import random


A, B = [int(str) for str in input().split()]

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

def is_prime(q,k=2):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし(但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


prime_list = [1] + [i for i in range(1, gcd(A, B) + 1) if is_prime(i)]
print(len([i for i in prime_list if A % i == 0 and B % i == 0]))

### FIXED CODE ###

A, B = [int(str) for str in input().split()]

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


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


print(len(set(prime_factorize(gcd(A, B)))) + 1)
### BUGGY CODE ###

N, M = [int(_) for _ in input().split()]
ab = [input().split() for _ in range(M)]
N = str(N)

ne = []
for i in ab:
    if i[0] == "1":
        ne += [i[1]]

for j in ab:
    if j[0] in ne and j[1] == N:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

### FIXED CODE ###

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

goal = {i:0 for i in range(1, N+1)}
N = str(N)

ne = []
for i in ab:
    if i[0] == "1":
        goal[int(i[1])] = 1

for j in ab:
    if goal[int(j[0])] and j[1] == N:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

import sys
import heapq 
input = sys.stdin.readline
n,m = map(int,input().split())
alwork = [() for i in range(10**5+1)]
w = []
hpop = heapq.heappop
hpush = heapq.heappush
ans = 0

for i in range(n):
  a,b = map(int,input().split())
  alwork[a] += (-b,)

for i in range(1,m+1):
  for j in alwork[i]:
    hpush(w,j)
  if w:
    ans += hpop(w)
print(-ans)

### FIXED CODE ###

import sys
import heapq 
input = sys.stdin.readline
n,m = map(int,input().split())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort(reverse=True)

w = []
hpop = heapq.heappop
hpush = heapq.heappush
ans = 0

for i in range(1,m+1):
  while l and l[-1][0]==i:
    hpush(w,-l.pop()[1])
  if w:
    ans += hpop(w)
print(-ans)
### BUGGY CODE ###

l, r = map(int, input().split())

from itertools import combinations

ans = [(x1*x2)%2019 for (x1, x2) in combinations(range(l, r+1), 2)]

print(min(ans))


### FIXED CODE ###

l, r = map(int, input().split())

from itertools import combinations

if r - l > 2019:
    r = l+2019

ans = [(x1*x2)%2019 for (x1, x2) in combinations(range(l, r+1), 2)]

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

import fractions


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

left_gcd_list = [a[0]]
right_gcd_list = [a[n - 1]]

for i in range(1, n):
    left_gcd_list.append(fractions.gcd(a[i], left_gcd_list[i - 1]))
    right_gcd_list.insert(0, fractions.gcd(a[n - 1 - i], right_gcd_list[0]))

print(max([left_gcd_list[n - 2]] +
          [fractions.gcd(left_gcd_list[i], right_gcd_list[i + 2]) for i in range(0, n - 2)] +
          [right_gcd_list[1]]))


if __name__ == '__main__':
    pass


### FIXED CODE ###

import fractions
import numpy as np


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

left_gcd_array = np.array([0] * n)
left_gcd_array[0] = a[0]

right_gcd_array = np.array([0] * n)
right_gcd_array[n - 1] = a[n - 1]

for i in range(1, n):
    left_gcd_array[i] = fractions.gcd(a[i], left_gcd_array[i - 1])
    right_gcd_array[n - 1 - i] = fractions.gcd(a[n - 1 - i], right_gcd_array[n - i])

print(max([left_gcd_array[n - 2]] +
          [fractions.gcd(left_gcd_array[i], right_gcd_array[i + 2]) for i in range(0, n - 2)] +
          [right_gcd_array[1]]))


if __name__ == '__main__':
    pass
### BUGGY CODE ###

s = input()
n = len(s)
ans = 0
for j in range(n, 3, -1):
    for i in range(j-4, -1, -1):
        num = int(s[i:j])
        if num % 2019 == 0:
            ans += 1
            break
 
print(ans)

### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0

cnts = [0] * 2019
cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0

for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)
### BUGGY CODE ###

N,A,B = map(int, input().split())
li = []
for i in range(A):
    li.append('b')
for i in range(B):
    li.append('r')

balls = A+B
an = 0
if N % balls == 0:
    print(int(A * (N/balls)))
else:
    an += A * (N//balls)
    for i in range(N % balls):
        if li[i] == 'b':
            an += 1
    print(an)

### FIXED CODE ###

N,A,B = map(int, input().split())
balls = A+B
an = 0
if N % balls == 0:
    print(int(A * (N//balls)))
else:
    an += A * (N//balls)
    an += min(A,N % balls)
    print(an)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000000)


def search(ai, bi, ti, ansi):
    global ans
    if ai < n and ti + a[ai] <= k:
        search(ai+1, bi, ti+a[ai], ansi+1)

    if bi < m and ti + b[bi] <= k:
        search(ai, bi+1, ti+b[bi], ansi+1)

    ans = max(ans, ansi)


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

ans = 0
search(0, 0, 0, 0)
print(ans)


### FIXED CODE ###

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

for i in range(1, N + 1):
    cumsum_a[i] = cumsum_a[i - 1] + A[i - 1]

for i in range(1, M + 1):
    cumsum_b[i] = cumsum_b[i - 1] + B[i - 1]

ans = 0
bi = M
for i in range(N+1):
    for j in range(bi, -1, -1):
        t = cumsum_a[i] + cumsum_b[j]
        if t <= K:
            ans = max(ans, i + j)
            bi = j
            break

print(ans)