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

from functools import reduce

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

def gcd(x,y):
	x_ = max(x,y)
	y_ = min(x,y)
	if y_==0:
		return 0
	if x_%y_==0:
		return y_
	return gcd(y_, x_%y_)

def gcd_list(numbers):
	return reduce(gcd, numbers)

gcds = [gcd_list(a[:i]+a[i+1:]) for i in range(n)]

print(max(gcds))


### FIXED CODE ###

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

def gcd(x_,y_):
	x = max(x_, y_)
	y = min(x_, y_)
	if y==0:
		return x
	if x%y == 0:
		return y
	return gcd(y, x%y)

L = [0]*n
R = [0]*n
L[0] = a[0]
R[-1] = a[-1]

for i in range(1,n):
	L[i] = gcd(L[i-1], a[i])
	j = n-1-i
	R[j] = gcd(R[j+1], a[j])

L = [0]+L
R = R + [0]
M = [0]*n
for i in range(n):
	M[i] = gcd(L[i],R[i+1])
print(max(M))
### BUGGY CODE ###

# from pprint import pprint
# import math
# import collections
from numba import jit

N = int(input())


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

@jit(cache=True)
def calc(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


from pprint import pprint

p = []
p_equal = []
for x in range(1, 100):
    for y in range(x, 100):
        for z in range(y, 100):
            p.append((x, y, z))
p_set = set(p)

p_equal = []
p_nonequal = []
for _p in p_set:
    x, y, z = _p[0], _p[1], _p[2]

    if x == y == z:
        p_equal.append(calc(x, y, z))
    else:
        p_nonequal.append(calc(x, y, z))

# print(p_equal)
# print(p_nonequal)

for i in range(1, N + 1):
    if i in p_equal:
        print(1)
    elif i in p_nonequal:
        print(3)
    else:
        print(0)


### FIXED CODE ###

# from pprint import pprint
# import math
# import collections
from numba import jit

N = int(input())

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

@jit(cache=True)
def calc(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


res = [0] * 1000009

for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            n = calc(x, y, z)
            res[n - 1] += 1

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

#
N=int(input())
S=[]
for i in range(N):
    S.append(input())
ans=[]

#
while len(S):
    if len(S)==1:
        x = [S.pop(0), 1]
        ans.append(x)
        break
    x = [S.pop(0), 1]
    for i in S[:]:
        if x[0] == i:
            S.remove(i)
            x[1]+=1
    ans.append(x)
ans.sort()
ans.sort(key=lambda x:x[1],reverse=True)

for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])


### FIXED CODE ###

#
N=int(input())
S={}
for i in range(N):
    x=input()
    if x in S:
        S[x]+=1
    else:
        S[x]=1
t=max(S.values())
ans=[k for (k,v) in S.items() if v==t]
ans.sort()

for i in ans:
    print(i)
""""
#
while len(S):
    if len(S)==1:
        x = [S.pop(), 1]
        ans.append(x)
        break
    x = [S.pop(), 1]
    for i in S[:]:
        if x[0] == i:
            S.remove(i)
            x[1]+=1
    ans.append(x)
ans.sort()
ans.sort(key=lambda x:x[1],reverse=True)

for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])



import queue

q=queue.Queue()
for i in S:
    q.put(i)

while not q.empty():
    x = [q.get(), 1]
    if len(ans)==0:
        ans.append(x)
        continue
    t=0
    for i in range(len(ans)):
        if x[0] == ans[i][0]:
            ans[i][1]+=1
            t+=1
            break
    if t==0:
        ans.append(x)
ans.sort()
ans.sort(key=lambda x:x[1],reverse=True)

for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])

"""
### BUGGY CODE ###

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

dist = [abs(a[i + 1] - a[i]) for i in range(len(a) - 1)]

for i in range(1, n + 1):
    ans = sum(dist) - abs(a[i] - a[i - 1]) - abs(a[i + 1] - a[i]) + abs(a[i - 1] - a[i + 1])
    print(ans)


### FIXED CODE ###

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

dist = [abs(a[i + 1] - a[i]) for i in range(len(a) - 1)]
total = sum(dist)

for i in range(1, n + 1):
    ans = total - abs(a[i] - a[i - 1]) - abs(a[i + 1] - a[i]) + abs(a[i - 1] - a[i + 1])
    print(ans)
### BUGGY CODE ###

#D
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = []
c = []
for _ in range(m):
    tmp = list(map(int, input().split()))
    b.append(tmp[0])
    c.append(tmp[1])
#print(b,c)
a.sort()
for i in range(m):
    a += [c[i]] * b[i]
    #print(i,a)
    a=sorted(a,reverse=True)
    a = a[:n]
    #print(i,a)
print(sum(a))

### FIXED CODE ###

#D
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
d = []
for i in range(m):
    b, c = map(int, input().split())
    d.append([b, c])
#print(d)
d = sorted(d, key=lambda x: x[1], reverse=True)
#print(d)
k = 0
for i in range(n):
    if d[k][0] == 0:#追加できなくなる
        k += 1
        if k == len(d):  #配列末
            break
    if a[i] >= d[k][1]:  #a>=cなのでこれ以上置き換わっても意味がない
        break
    a[i] = d[k][1]  #cに置き換わった
    d[k][0] -= 1  #dの追加出来る数を１減らす
print(sum(a))
### BUGGY CODE ###

import numpy as np

N,W = map(int,input().split())
dp = np.zeros((N+2,W+2), dtype=int)

for i in range(1,N+1):
  w,v = map(int,input().split())
  for j in range(1,W+1):
    if j >= w:
      dp[i+1][j] = max(dp[i][j-w]+v,dp[i][j])
    else: # j < w
      dp[i+1][j] = dp[i][j]

print(dp[-1][-2]) 

### FIXED CODE ###

import numpy as np

N,W = map(int,input().split())
dp = np.zeros(W+1, dtype=int)

for i in range(N):
  w,v = map(int,input().split())
  dp[w:] = np.maximum(dp[w:],dp[:-w]+v)

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

n,m = map(int, input().split())
pre = {}
city = []
for i in range(m):
    p,y = map(int, input().split())
    if p not in pre:
        pre[p] = []
    pre[p].append(y)
    city.append((p,y))

for k in pre.keys():
    pre[k].sort()

for p,y in city:
    print(str(p).zfill(6) + str(pre[p].index(y)+1).zfill(6))
    

### FIXED CODE ###

from heapq import heappush, heappop
N,M = map(int, input().split())
A = {}
prefs = []
years = []
for i in range(M):
    p,y = input().split()
    prefs.append(p)
    years.append(y)
    if p not in A:
        A[p] = [int(y)]
    else:
        heappush(A[p], int(y))
res = {}
for k,v in A.items():
    for i in range(len(v)):
        res[k+str(heappop(v))] = str(i+1)
for p,y in zip(prefs, years):
    print(p.zfill(6) + res[p+y].zfill(6))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
n, m = map(int, input().split())
value = []
for i in range(m):
    A, B = map(int, input().split())
    c = sum(1<<(ci-1) for ci in map(int, input().split()))
    value.append([A, c])
    
dp = [100100100] * (1<<n)
dp[0] = 0
for s in range(1<<n):
    for i in range(m):
        t = s | value[i][1]
        cost = dp[s] + value[i][0]
        dp[t] = min(dp[t], cost)
if dp[(1<<n)-1] == 100100100:
    print(-1)
else:
    print(dp[(1<<n)-1])

### FIXED CODE ###

#import sys
#input = sys.stdin.readline
 
n, m = map(int, input().split())
value = []
for i in range(m):
    A, B = map(int, input().split())
    c = sum(1<<(ci-1) for ci in map(int, input().split()))
    value.append([A, c])
    
dp = [100100100] * (1<<n)
dp[0] = 0
for s in range(1<<n):
    for i in range(m):
        t = s | value[i][1]
        cost = dp[s] + value[i][0]
        if dp[t] > cost:
            dp[t] = cost
        
if dp[(1<<n)-1] == 100100100:
    print(-1)
else:
    print(dp[(1<<n)-1])
### BUGGY CODE ###

import sys

N,Q = [int(i) for i in sys.stdin.readline().split()]
D=[10**10]*N
D[0]=0
A=[[0]*3 for i in range(N-1)]
Ans=[0]*N
P=[[0]*2 for i in range(Q)]

for i in range(N-1):
    A[i][0],A[i][1] = [int(i) for i in sys.stdin.readline().split()]
    if(A[i][0]==1):
        D[A[i][1]-1]=1
    else:
        D[A[i][1]-1]=D[A[i][0]-1]+1
    A[i][2]=D[A[i][1]-1]
while(max(D)>(10**10)):
    for i in range(N-2,-1,-1):
        if(D[i]>(10**10)):
            D[A[i][1]-1]=D[A[i][0]-1]+1
        A[i][2]=D[A[i][1]-1]

for i in range(Q):
    P[i][0],P[i][1] = [int(i) for i in sys.stdin.readline().split()]
    Ans[P[i][0]-1]+=P[i][1]
A=sorted(A,key=lambda x: x[2])

for i in range (N-1):
    Ans[A[i][1]-1]+=Ans[A[i][0]-1]
print(*Ans)


### FIXED CODE ###

import sys

n, q = [int(i) for i in sys.stdin.readline().split()]
graph = {i: [] for i in range(n)}
ct = [0 for i in range(n)]
for i in range(n - 1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

for i in range(q):
    p, x = [int(i) for i in sys.stdin.readline().split()]
    p -= 1
    ct[p] += x
already = {0}
stack = [(0, ct[0], -1)]
res = [0 for i in range(n)]
while len(stack) > 0:
    cur, cost, _from = stack.pop(-1)
    res[cur] = cost
    for _next in graph[cur]:
        if _next == _from:
            continue
        next_cost = ct[_next]
        stack.append((_next, cost + next_cost, cur))
        already.add(cur)
print(" ".join([str(r) for r in res]))
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
l = [list(map(int,input().split())) for i in range(q)]

for i in range(q):
    print(s[l[i][0]-1:l[i][1]].count('AC'))


### FIXED CODE ###

n,q = map(int,input().split())
s = input()
t = [0]*(n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2]=="AC" else 0)
for i in range(q):
    l,r = map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

from collections import deque
from collections import Counter

n = int(input())
a = [int(x) for x in input().split()]
d = deque(a)
e = deque([])
# print(d)
for i in range(n):
    ans = 0
    a = d.popleft()
    c = Counter(d)
    # print(c)
    for j in c.values():
        # print(j)
        ans += (j-1)*j//2
    # print(ans, d)
    e.append(ans)
    d.append(a)
    
for k in e:
    print(k)

### FIXED CODE ###

from collections import Counter

n = int(input())
a = [int(x) for x in input().split()]
s = 0
c = Counter(a)
# print(c)
for i in c.values():
    s += i*(i-1)// 2
    
# print(s)
for j in range(n):
    t = c[a[j]]
    print(s-t+1)
### BUGGY CODE ###

# coding: utf-8
import sys
from fractions import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

N = ir()
A = lr()
lcm = 1
for a in A:
    lcm *= a // gcd(lcm, a)

answer = 0
for a in A:
    answer += lcm // a

print(answer % MOD)
# np.int64とint型の違いに注意

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
#リストの最小公倍数
def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort()
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) #B[0]
answer = x%MOD

for i in range(1, N):
    answer += first * x // A[i]

print(answer%MOD)
### BUGGY CODE ###

import itertools
import math
N = int(input())
for n in range(1, N+1):
  ans = 0
  if n > 5:
    n_max = int(math.sqrt(n))
    l = [i for i in range(1, n_max)]
    for c in itertools.combinations_with_replacement(l, 3):
      if n == c[0]**2 + c[1]**2 + c[2]**2 + c[0]*c[1] + c[0]*c[2] + c[1]*c[2]:
        if len(set(c)) == 1:
          ans += 1
        elif len(set(c)) == 2:
          ans += 3
        elif len(set(c)) == 3:
          ans += 6
  print(ans)

### FIXED CODE ###

import itertools
import math
import numpy as np

N = int(input())

n_max = int(math.sqrt(N))
l = [i for i in range(1, n_max)]
score = np.zeros([10000]).astype(np.uint8)
for c in itertools.combinations_with_replacement(l, 3):
  sum = c[0]**2 + c[1]**2 + c[2]**2 + c[0]*c[1] + c[0]*c[2] + c[1]*c[2]
  if sum <= 10000:
    if len(set(c)) == 3:
      score[sum-1] += 6
    elif len(set(c)) == 2:
      score[sum-1] += 3
    else:
      score[sum-1] += 1
    
for n in range(1, N+1):
  ans = 0
  print(score[n-1])
### BUGGY CODE ###

N = int(input())
S =  input()
max_length = 0
for i in range(N):
    max_j = (N -i)//2
    for j in range(max_j):
        current_length = max_j-j
        if S[i:i+current_length] in S[i+current_length:N]:
            if current_length > max_length:
                max_length = current_length
            break
print(max_length)

### FIXED CODE ###

n = int(input())
S = input()
N = [0]*n
j = 0
 
for i in range(n):
  while S[i:j] in S[j:n]:
    N[i] = j-i
    j += 1
    
print(max(N))
### BUGGY CODE ###

N,M=map(int, input().split())
S=input()
now=S[N-1]
dp=[float("INF")]*(N+1)
dp[N]=0
for i in range(N-1,-1,-1):
    if S[i]=="1":
        continue
    else:
        dp[i]=1+min(dp[i+1:i+1+M])
#print(dp)
#print(dp[0])
now=dp[0]
nowi=0
if now==float("INF"):
    print(-1)
    exit()
for i in range(1,N+1):
    if now>dp[i]:
        print(i-nowi, end=" ")
        now=dp[i]
        nowi=i


### FIXED CODE ###

N,M=map(int, input().split())
S=input()
now=S[N-1]
dp=[float("INF")]*(N+1)
dp[N]=0
nowmin=0
right=N
for left in range(N-1,-1,-1):
    while right-left>M or S[right]=="1":
        right-=1
        nowmin=dp[right]
    if right<=left:
        print(-1)
        exit()
    if S[left]=="1":
        continue
    else:
        dp[left]=1+nowmin
#print(dp)
#print(dp[0])
now=dp[0]
nowi=0
"""
if now==float("INF"):
    print(-1)
    exit()
"""
for i in range(1,N+1):
    if now>dp[i]:
        print(i-nowi, end=" ")
        now=dp[i]
        nowi=i
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
ans=[]
#n=int(raw_input())
#for _ in range(n):
for _ in range(int(raw_input())):
    a=sys.stdin.readline().split()
    chk=a[0]
    if chk=='insert': ans.insert(0,a[1])
#    elif chk=='deleteFirst': ans.pop(0)
    elif chk=='deleteFirst': del ans[0]
#    elif chk=='deleteLast': ans.pop()
    elif chk=='deleteLast': del ans[-1]
#    else: ans.remove(str(a[1]))
    else:
#        if a[1] in ans:
        if ans.count(a[1])>0:
            ans.remove(a[1])
#    print ans
print ' '.join(ans)

### FIXED CODE ###

import sys
import collections
n=int(raw_input())
ans=collections.deque()
while n:
    n-=1
    s=sys.stdin.readline().rstrip().split(' ')
    if s[0][0]=='i':
        ans.appendleft(s[1])
    elif s[0][-3]=='r':
        ans.popleft()
    elif s[0][-3]=='a':
        ans.pop()
    else:
        try:
            ans.remove(s[1])
        except:
            pass
sys.stdout.write(' '.join(ans))
print
### BUGGY CODE ###

a = int(input())
b = list(map(int, input().split()))
for i in range(a+1):
        if sum(b[0:i-1]) == sum(b)/2:
            print(0)
        if sum(b[0:i-1]) < sum(b)/2 < sum(b[0:i]):
                v = sum(b[0:i])- (sum(b)-sum(b[0:i]))
                u = (sum(b)-sum(b[0:i - 1]))-sum(b[0:i -1])
                print(min(v,u)) 

### FIXED CODE ###

a = int(input())
b = list(map(int, input().split()))
import bisect
ln = []
x = 0
for i in b:
    x += i
    ln.append(x)
index = bisect.bisect_left(ln, sum(b)/2)
if sum(b[0:index -1]) == sum(b)/2:
            print(0)
else:
                v =  sum(b[0:index + 1])- (sum(b)-sum(b[0:index + 1]))
                u = (sum(b)-sum(b[0:index]))-sum(b[0:index])
                print(min(v,u))
### BUGGY CODE ###

n, m = [int(_) for _ in input().split(' ')]
print(max([i for i in range(1, m // n + 1) if m % i == 0]))


### FIXED CODE ###

n, m = [int(_) for _ in input().split(' ')]

ds = [i for i in range(1, int(m ** 0.5) + 1) if m % i == 0]
ds.extend([m // i for i in ds])
print(max([i for i in ds if i <= m // n]))
### BUGGY CODE ###

l, r = map(int, input().split())
if l <= 2019 <= r:
    print(0)
    exit()
elif r*(r-1) <= 2019:
    print(l*(l+1))
    exit()

a = 2019
for i in range(l, r):
    for j in range(i+1, r+1):
        a = min(a, (i*j)%2019)

print(a)


### FIXED CODE ###

l, r = map(int, input().split())
if l <= 2019 <= r:
    print(0)
    exit()
elif r*(r-1) <= 2019:
    print(l*(l+1))
    exit()

a = 2019
for i in range(l, r):
    for j in range(i+1, r+1):
        a = min(a, i*j%2019)
        if a == 0:
            print(0)
            exit()

print(a)
### BUGGY CODE ###

#!/usr/bin/python3

import sys
#from collections import deque
#from copy import copy
#from bisect import bisect_right, bisect_left
#import array
from scipy.sparse.csgraph import dijkstra

N = int(input())

V = [[0]*N for _ in range(N)]

for i in range(N-1):
    u,v,w = list(map(int, input().split()))
    V[u-1][v-1] = w

D = dijkstra(V, directed=False, indices=0)
#print(D)

for i in range(0,N):
    if D[i] % 2 == 0: #even
        print(0)
    else:
        print(1)


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import numpy
#from collections import deque
sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

childsof = [[] for _ in range(N+1)]

for _ in range(N-1):
    u,v,w = list(map(int, input().split()))
    childsof[u].append((v,w))
    childsof[v].append((u,w))

distances = [-1]*(N+1)
distances[1] = 0

def dfs(i):
    childs = childsof[i]

    for c in childs:
        j = c[0]
        if distances[j] == -1:
            distances[j] = distances[i] + c[1]
            dfs(j)

dfs(1)

for d in distances[1:]:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)
### BUGGY CODE ###

a, b, k = map(int, input().split())
if b-a+1 >= 2*k:
    l = [i for i in range(a, b + 1)]
    ans = sorted(l[:k] + l[-k:])
else:
    ans = [i for i in range(a, b + 1)]
for i in ans:
    print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())

l = [i for i in range(A, A + K) if i <= B]
li = l + [i for i in range(B - K + 1, B + 1) if i >= A]

for i in sorted(set(li)):
    print(i)
### BUGGY CODE ###

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

ans = []
for i in range(1, N+1):
    x = A.count(i)
    ans.append(x)

print(*ans, sep='\n')


### FIXED CODE ###

import collections

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

ans = collections.Counter(A)

for n in range(N):
    print(ans[n+1])
### BUGGY CODE ###

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

### FIXED CODE ###

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

n = int(input())
S = input()
m = n//2
l,r = 0,n-1
ans = 0
while l<=r:
    m = (l + r) // 2
#    print("m = ", m)
    for i in range(n-m) :
        # 切り取る
        sub = S[i :i + m]
#        print("sub=", sub)
#        print("i=", i)
        fl = False
        Se = set()
        for j in range(i+m,n - m + 1) :
            sub2 = S[j :j + m]
            Se.add(sub2)
#            print("j=", j, Se)
        if sub in Se:
            fl = True
            l = m+1
            ans = l-1
#            print(l-1,"にて共通部分有")
            break
    else:
        r = m-1
#        print(r+1,"にて共通部分無")
print(ans)

### FIXED CODE ###

n = int(input())
S = input()
m = n//2
l,r = 0,n-1
ans = 0
def check(m):
    Se = set()
    for i in range(n-2*m+1):
        Se.add(S[i:i+m])
        if S[i+m:i+2*m] in Se:
            return True
    return False

while l<=r:
    m = (l + r) // 2
 #   print("m = ", m)
    if check(m):
        fl = True
        l = m+1
        ans = l-1
 #       print(l-1,"にて共通部分有")
    else:
        r = m-1
 #       print(r+1,"にて共通部分無")
print(ans)
### BUGGY CODE ###

import math

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


q = int(input())
l_r = []
for _ in range(q):
    l, r = map(int, input().split())
    l_r.append((l,r))

can = primes(10**5)
like_2017 = []

for m in can:
    limit = (max(can)//2)
    if m > limit :
        break
    if 2*m-1 in can:
        like_2017.append(2*m-1)

count = 0
can_count = []
for i in range(10**5):
    if i in like_2017:
        count += 1
    else:
        pass
    can_count.append(count)

for pair in l_r:
    l = pair[0]
    r = pair[1]
    ans = can_count[r] - can_count[l-1]
    print(ans)

    


### FIXED CODE ###

import math

def Sieve_of_Eratosthenes(n):
    if n < 2:
        raise ValueError('n is more than 2.')
    prime = []
    limit = math.sqrt(n)
    can = [i for i in range(2, n+1)]
    while True:
        p = can[0]
        if limit <= p:
            return prime + can
        prime.append(p)
        can = [x for x in can if x%p != 0]

q = int(input())
l_r = []
for _ in range(q):
    l, r = map(int, input().split())
    l_r.append((l,r))

can = Sieve_of_Eratosthenes(10**5)
like_2017 = []

for m in can:
    limit = (max(can)//2)
    if m > limit :
        break
    if 2*m-1 in can:
        like_2017.append(2*m-1)

count = 0
can_count = []
for i in range(10**5):
    if i in like_2017:
        count += 1
    else:
        pass
    can_count.append(count)

for pair in l_r:
    l = pair[0]
    r = pair[1]
    ans = can_count[r] - can_count[l-1]
    print(ans)
### BUGGY CODE ###

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

zero = 0

for i in range(n):
  total = 0
  for j in a[i:]:
    total += j
    if total == 0:
      zero += 1

print(zero)

### FIXED CODE ###

import math

n = int(input())
zero = 0
total_dictionary = {0: 1}
total = 0

for i in input().split():
  total += int(i)
  zero += total_dictionary.get(total,0)
  if total in total_dictionary:
    total_dictionary[total] += 1
  else:
    total_dictionary[total] = 1

print(zero)
### BUGGY CODE ###

N=int(input())
q=[]  
for i in range(N):
    q+=[list(input())]
    q[i].sort()
    q.sort()
m=0
s=0
z=0 #総得点
while m<N-1:
    if q[m]!=q[m+1]:
        z+=((s*(s+1))//2)
        s=0
    else:
        s+=1
    m+=1
z+=((s*(s+1))//2)
print(z)

### FIXED CODE ###

N=int(input())
q=[]  
for i in range(N):
    q+=[list(input())]
    q[i].sort()
q.sort() 
i=0
s=0
z=0 #総得点
while i<N-1:
    if q[i]!=q[i+1]:
        z+=((s*(s+1))//2)
        s=0
    else:
        s+=1
    i+=1
z+=((s*(s+1))//2)
print(z)
### BUGGY CODE ###

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
cnt = 0
for i in a:
    flag = True
    for j in divisor(i):
        if j in a[a.index(i) + 1:]:
            flag = False
    if flag:
        cnt += 1
print(cnt)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m = 10 ** 6 + 1
cnt = [0] * m
for x in a:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    for i in range(x, m, x):
        cnt[i] += 1
ans = 0
for x in a:
    if cnt[x] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

import re
S = input()
a = S
while True:
  b = re.sub('01|10','',a)
  if len(a) == len(b):
    break
  else:
    a = b
print(len(S)-len(a))

### FIXED CODE ###

S = input()
print(min(S.count('0'),S.count('1'))*2)
### BUGGY CODE ###

n = int(input())
m = list(map(int,input().split()))
s=1
for i in range(n):
  s=s*m[i-1]
if s > 10**18:
  print(-1)
else:
  print(s)

### FIXED CODE ###

import numpy
n = int(input())
m = list(map(int,input().split()))
s = 1
a = 0
if 0 in m:
  print(0)
  a =1
else:
  for i in range(n):
    s=s*m[i-1]
    if s>10**18:
      print(-1)
      a = 1
      break
if a == 0:
  print(s)