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

INF = 10**10 - 1


#指定数分の３つの整数を順番に受けてリストに入力
# スペース区切りの整数入力
N,Wmax = map(int, input().split())
w = [0]*(N+1)
v = [0]*(N+1)
for i in range(1,N+1):
    w[i],v[i] = map(int, input().split())

#dpの初期化
dp = [[-INF] * (Wmax+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0
#print(dp[0])

for i in range(1,N+1):
    for ww in range(1,Wmax+1):
        dp[i][ww] = dp[i-1][ww]        
        if w[i] > ww:
            continue
        else:
            dp[i][ww] = max(dp[i][ww],dp[i-1][ww-w[i]]+v[i])
    #print(dp[i])

Vmax = 0
for ww in range(1,Wmax+1):
    Vmax = max(Vmax,dp[N][ww])
print(Vmax)


### FIXED CODE ###

INF = 10**10 - 1


#指定数分の３つの整数を順番に受けてリストに入力
# スペース区切りの整数入力
N,Wmax = map(int, input().split())
w = [0]*(N+1)
v = [0]*(N+1)
for i in range(1,N+1):
    w[i],v[i] = map(int, input().split())

#dpの初期化
dp = [[-INF] * (Wmax+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0
#print(dp[0])

for i in range(1,N+1):
    for ww in range(1,Wmax+1):
        dp[i][ww] = dp[i-1][ww]        
        if w[i] > ww:
            continue
        else:
            dp[i][ww] = max(dp[i][ww],dp[i-1][ww-w[i]]+v[i])
    #print(dp[i])

Vmax = 0
for ww in range(1,Wmax+1):
    Vmax = max(Vmax,dp[N][ww])
print(Vmax)
### BUGGY CODE ###

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

def ctoi(c):
    return ord(c) - ord('a')

class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w): # 0-indexed
        x += 1
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def _sum(self,x): # 1-indexed
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
    def sum(self,l,r): # [l,r)
        return self._sum(r) - self._sum(l)
    def __str__(self): # for debug
        arr = [self.sum(i,i+1) for i in range(self.N)]
        return str(arr)
bits = [BinaryIndexedTree(N) for i in range(26)]

s = []
for i,c in enumerate(S):
    bits[ctoi(c)].add(i,1)
    s.append(c)

ans = []
for a,b,c in qs:
    if a=='1':
        i = int(b)-1
        bits[ctoi(s[i])].add(i,-1)
        bits[ctoi(c)].add(i,1)
        s[i] = c
    else:
        l,r = int(b)-1,int(c)
        a = 0
        for i in range(26):
            if bits[i].sum(l,r):
                a += 1
        ans.append(a)
print(*ans,sep='\n')

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
S = input().rstrip()
Q = int(input())
qs = [input().split() for i in range(Q)]

def ctoi(c):
    return ord(c) - ord('a')

bit = [[0]*(N+2) for _ in range(26)]
def bit_add(x,w,ci):
    while x <= N+1:
        bit[ci][x] += w
        x += (x & -x)
def bit_sum(x,ci):
    ret = 0
    while x > 0:
        ret += bit[ci][x]
        x -= (x & -x)
    return ret

for i,c in enumerate(S):
    bit_add(i+1,1,ctoi(c))

s = list(S)
ans = []
for a,b,c in qs:
    if a=='1':
        x = int(b)
        bit_add(x,1,ctoi(c))
        bit_add(x,-1, ctoi(s[x-1]))
        s[x-1] = c
    else:
        tmp = 0
        for i in range(26):
            if bit_sum(int(c),i) - bit_sum(int(b)-1,i) > 0:
                tmp += 1
        ans.append(tmp)
print(*ans, sep='\n')
### BUGGY CODE ###

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


mid_dis = [abs(a[n-1] / 2 - a[i]) for i in range(n-1)]
arg_max_i = [i for i in range(n-1) if mid_dis[i] == min(mid_dis)][0]

print(a[n-1], a[arg_max_i])

### FIXED CODE ###

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

import bisect

arg_max_i = bisect.bisect_left(a, a[n-1] // 2)

if abs(a[n-1] / 2 - a[arg_max_i]) > abs(a[n-1] / 2 - a[arg_max_i-1]):
  arg_max_i -= 1
if arg_max_i == n-1:
  arg_max_i -= 1

print(a[n-1], a[arg_max_i])
### BUGGY CODE ###

def main():
  n, p = map(int, input().split()) 
  s = input() 

  ans = 0

  if p == 2:
    for i, si in enumerate(s):
      if int(si) % 2 == 0:
        ans += (i+1)
    print(ans)
    exit()

  if p == 5:
    for i, si in enumerate(s):
      if int(si) % 5 == 0:
        ans += (i+1)
    print(ans)
    exit()

  rem_dict = {i: 0 for i in range(p)}

  for i in range(n):
    rem = int(s[i:]) % p
    ans += rem_dict[rem]
    if rem == 0:
      ans += 1      
    rem_dict[rem] += 1

  print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  n, p = map(int, input().split()) 
  s = input() 

  ans = 0

  if p == 2:
    for i, si in enumerate(s):
      if int(si) % 2 == 0:
        ans += (i+1)
    print(ans)
    exit()

  if p == 5:
    for i, si in enumerate(s):
      if int(si) % 5 == 0:
        ans += (i+1)
    print(ans)
    exit()

  rem_list = [0] * p
  cof = 1
  prev_rem = 0
  
  for i in range(n):
    rem = (int(s[n-1-i]) * cof + prev_rem) %  p
    ans += rem_list[rem]
    if rem == 0:
      ans += 1      
    rem_list[rem] += 1

    prev_rem = rem
    cof *= 10
    cof %= p

  print(ans)

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

N, M = map(int, input().split())
dic = {}
raw = []
dic[1] = []
for i in range(M):
  P, Y = map(int, input().split())
  raw.append([P, Y])
  dic.setdefault(P, list())
  dic[P].append(Y)
for i in dic.keys():
  try:
    dic[i].sort()
  except:
    continue
for i in range(M):
  P, Y = raw[i]
  ind = dic[P].index(Y)
  P = "{0:06d}".format(P)
  Y = "{0:06d}".format(ind+1)
  print(P+Y)

### FIXED CODE ###

N, M = map(int, input().split())
dic = {}
raw = []
dic[1] = []
for i in range(M):
  P, Y = map(int, input().split())
  raw.append([P, Y, i])
raw.sort()
for i in range(M):
  if i == 0:
    raw[i][1] = 1
    p, y, ind = raw[i]
    continue
  pp, yy, iind = raw[i]
  if pp == p:
    raw[i][1] = y + 1
  else:
    raw[i][1] = 1
  p, y, ind = raw[i]
raw.sort(key = lambda x:x[2])
for r in raw:
    p, y, ind = r
    P = "{0:06d}".format(p)
    Y = "{0:06d}".format(y)
    print(P+Y)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans=1
for i in range(N):
    ans=ans*A[i]
print(ans if ans<=1000000000000000000 else "-1")

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans=1
i=0
while ans<=1000000000000000000 and i<N:
    ans=ans*A[i]
    i+=1

if A.count(0)>0:
    print(0)
else:
    print(ans if ans<=1000000000000000000 else "-1")
### BUGGY CODE ###

while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n)]for j in range(n)]
    for i in range(n):
        j=0
        for c in raw_input():
            if c == ".":
                dp[i][j]=1
            j+=1
    while True:
        flag=0
        for y in range(n-1):
            for x in range(n-1):
                if dp[y][x]!=0:
                    old=dp[y][x]
                    dp[y][x]=min(dp[y+1][x],dp[y][x+1],dp[y+1][x+1])+1
                    if old!=dp[y][x]:
                        flag=1
        if flag==0:
            break
    allmax=0
    for i in range(n):
        if allmax<max(dp[i]):
            allmax=max(dp[i])
    print allmax

### FIXED CODE ###

while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n+1)]for j in range(n+1)]
    for i in range(1,n+1):
        j=0
        line=" "+raw_input()
        for c in line:
            if c == ".":
                dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
            j+=1
    allmax=0
    for i in range(n+1):
        if allmax<max(dp[i]):
            allmax=max(dp[i])
    print allmax
### BUGGY CODE ###

S = input()

N = len(S)

S=list(S)

c=0
while(1):
    f=0
    for i in range(N-1):
        #print(i, S, N)                                                                  
        if S[i] != S[i+1]:
            del S[i:i+2]
            c+=2
            N-=2
            f=1
            break
    if f==0:
        break
print(c)

### FIXED CODE ###

S = list(input())
N = len(S)

c=0
i=0
f=0
while(1):
    if i+1 == N or N < 2:
        break
    if S[i] != S[i+1]:
        del S[i:i+2]
        c += 2
        N -= 2
        if i >= 1:
            i -= 2
        else:
            i -= 1
    i += 1
    #print(i,N,S,f)                                                                      
print(c)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
N, Q = map(int, input().split())
evs = [None] * 2*N
for i in range(N):
    s, t, x = map(int, input().split())
    evs[2*i] = [s-x, 1, x]
    evs[2*i+1] = [t-x, -1, x]
evs.sort()
s = set()
h = []
dic = defaultdict(int)
i, NN = 0, 2*N
for q in range(Q):
    d = int(input())
    while i < NN and evs[i][0] <= d:
        r, f, x = evs[i]
        if f == 1:
            s.add(x)
            heappush(h, x)
            dic[x] += 1
        else:
            s.remove(x)
            dic[x] -= 1
        i += 1
    if len(s):
        while h:
            p = heappop(h)
            if dic[p] > 0:
                heappush(h, p)
                break
        print(p)
    else:
        print(-1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
INF = float('inf')

class SegmentTree:

    def __init__(self, N):
        self.N = 1<<(N-1).bit_length()
        self.data = [None] * (2*self.N)

    def Update(self, l, r, t, v):
        L, R, val = l+self.N, r+self.N, (t, v)
        while L < R:
            if R & 1:
                R -= 1
                self.data[R-1] = val
            if L & 1:
                self.data[L-1] = val
                L += 1
            L >>= 1
            R >>= 1

    def getValue(self, x):
        x += self.N-1
        ret = (-1, INF)
        while x >= 0:
            if self.data[x]:
                ret = max(ret, self.data[x])
            x = (x-1)//2
        return ret[1]

N, Q = map(int, input().split())
stx = [[int(x) for x in input().split()] for i in range(N)]
stx.sort(key = lambda v : -v[2])
D = [(int(input()), i) for i in range(Q)]
D.sort(key = lambda v : v[0])
d, p = [d for d, p in D], [p for d, p in D]
seg = SegmentTree(Q)
for i, (s, t, x) in enumerate(stx):
    l = bisect_left(d, s-x)
    r = bisect_left(d, t-x)
    seg.Update(l, r, i, x)
ans = [None] * Q
for i in range(Q):
    tmp = seg.getValue(i)
    if tmp == INF:
        tmp = -1
    ans[p[i]] = tmp
print(*ans, sep = '\n')
### BUGGY CODE ###

#####segfunc######
def segfunc(x,y):
    return max(x,y)

def init(init_val):
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res
    
n,k = map(int,input().split())
a = [int(input()) for i in range(n)]
#n = int(input())
#a = tuple(map(int,input().split()))

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(max(a)-1).bit_length()
seg=[ide_ele]*2*num
#init(a)

ans = 0

for i in range(n):
    tmp = query(max(0,a[i]-k),min(a[i]+k+1,max(a)+1))
    #print(i,a[i],max(0,a[i]-k),min(a[i]+k,max(a)))
    update(a[i],tmp+1)
    #print(tmp)
    #print(st.query(0, max(a)))
    #ans = max(ans,tmp+1)
    #print(seg[0],k)
#print(seg)
#print(query(0,max(a)),seg[0])
print(seg[0])

### FIXED CODE ###

#####segfunc######
def segfunc(x,y):
    return max(x,y)

def init(init_val):
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res
    
n,k = map(int,input().split())
a = [int(input()) for i in range(n)]
#n = int(input())
#a = tuple(map(int,input().split()))

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(max(a)-1).bit_length()
seg=[ide_ele]*2*num
#init(a)

ans = 0
max_a = max(a)

for i in range(n):
    tmp = query(max(0,a[i]-k),min(a[i]+k+1,max_a+1))
    #print(i,a[i],max(0,a[i]-k),min(a[i]+k,max(a)))
    update(a[i],tmp+1)
    #print(tmp)
    #print(st.query(0, max(a)))
    #ans = max(ans,tmp+1)
    #print(seg[0],k)
#print(seg)
#print(query(0,max(a)),seg[0])
print(seg[0])
### BUGGY CODE ###

import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

def multiple(a, b):
    return a*b // euclid(a, b)

def lcm(nums):
        return functools.reduce(multiple, nums)

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

### FIXED CODE ###

import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

def multiple(a, b):
    return a*b // euclid(a, b)

def lcm(nums):
        return functools.reduce(multiple, nums)

X = lcm(A)
ans = 0
for i in range(N):
    ans += X//A[i]
ans %= MOD
print(ans)
### BUGGY CODE ###

MOD = 10**9+7
n = int(input())
A = list(map(int, input().split()))
ans = 0
for j in range(61):
  c = 0
  for i in A:
    if i>>j & 1:
      c += 1
  ans += 2**j*((n-c)*c)
  ans %= MOD
print(ans%MOD)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for j in range(61):
  c = 0
  for i in A:
    if i>>j & 1:
      c += 1
  ans += 2**j*((n-c)*c)
print(ans%(10**9+7))
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))

    max_average = 0
    point = 0
    for i in range(len(P)-K+1):

        if max_average < sum(P[i:i+K]):
            max_average = sum(P[i:i+K])
            point = i

    count = 0
    for p in range(point, point+K):
        count += sum(range(1, P[p]+1)) / P[p]

    print(count)

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))

    tmp_max = sum(P[:K])
    tmp = sum(P[:K])
    for i in range(N-K):
        tmp += P[i+K]
        tmp -= P[i]

        if tmp > tmp_max:
            tmp_max = tmp

    print((tmp_max + K) / 2)

main()
### BUGGY CODE ###

def main():
    N = int(input())
    L = list(map(int, input().split()))

    L = sorted(L, reverse=True)

    ans = 0
    for i in range(N):
        #tmp = 0

        for j in range((i+1), N):
            if L[i]/2 >= L[j]:
                break
            elif L[i] == L[j]:
                ans += len(L[j+1::])
                continue

            #for k in range((j+1), N):
            #    if L[i] < (L[j]+L[k]):
            #        ans += 1

            ans += len([t for t in L[j+1::] if L[i] < (L[j]+t)])





    
    print(ans)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))

    L = sorted(L)
    
    ans = 0
    for i in range(N-1):
        for j in range((i+1), N):    
            c = bisect.bisect_left(L, L[i] + L[j], j+1)
            ans += c - j - 1

    print(ans)


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

n=int(input())
a=list(map(int,input().split()))
x=1
for i in range(n):
  if a[0]==x:
    x+=1
  a.pop(0)

if x==1:
  ans=-1
else:
  ans=n-x+1

print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
x=1
for i in range(n):
  if a[i]==x:
    x+=1

if x==1:
  ans=-1
else:
  ans=n-x+1

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

import fractions

n, m = map(int, input().split())
a = list(map(int, input().split()))
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

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

now = a[0]
for i in range(1, n):
	now = lcm(now, a[i])

for i in range(n):
	if (now//a[i])%2 == 0:
		print(0)
		exit(0)

print(((m//(now//2))+1)//2)


### FIXED CODE ###

import fractions

n, m = map(int, input().split())
a = list(map(int, input().split()))
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

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

now = a[0]
for i in range(1, n):
	now = lcm(now, a[i])
	if now > 2 * m:
		print(0)
		exit(0)

for i in range(n):
	if (now//a[i])%2 == 0:
		print(0)
		exit(0)

print(((m//(now//2))+1)//2)
### BUGGY CODE ###

from itertools import *
from bisect import bisect_right
n,m,time = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

A = [0]+list(accumulate(a))
B = [0]+list(accumulate(b))

ans = 0
for i in range(bisect_right(A, time)-1,-1,-1):
    for j in range(bisect_right(B, time)-1,-1,-1):
        if A[i] + B[j] <= time:
            ans = max(ans,i+j)
print(ans)


### FIXED CODE ###


from itertools import *
from bisect import bisect_right
n,m,time = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

A = [0]+list(accumulate(a))
B = [0]+list(accumulate(b))

ans = 0
for i in range(bisect_right(A, time)-1,-1,-1):
    ans = max(ans,i+bisect_right(B, time-A[i])-1)
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())

white = 0
bcount = 0
wcount = 0
mins = []

for i in range(N):
    if S[i] == ".":
        white += 1

mins.append(white)
        
for i in range(N):
    for j in range(N):
        if (j <= i and S[j] == '#'):
            bcount += 1
        elif (i < j and S[j] == '.'):
            wcount += 1
    mins.append(bcount + wcount)
    bcount = 0
    wcount = 0

print(min(mins))


### FIXED CODE ###

N = int(input())
S = list(input())

bcount = 0
wcount = 0
mins = []

for i in range(N):
    if S[i] == ".":
        wcount += 1

mins.append(wcount)
        
for i in range(N):
    if S[i] == '#':
        bcount += 1
    else:
        wcount -= 1
    mins.append(bcount + wcount)

print(min(mins))
### BUGGY CODE ###

def solve():
    dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            for k in range(4):
                dp[i][j][k] = max(dp[i][j - 1][k], dp[i - 1][j][3])
            if (i, j) not in items:
                continue
            for k in range(3, 0, -1):
                dp[i][j][k] = max(dp[i][j][k], dp[i][j][k - 1] + items[(i, j)])
    return dp[R][C][3]


R, C, K, *rcv = map(int, open(0).read().split())

items = {}
for r, c, v in zip(*[iter(rcv)] * 3):
    items[(r, c)] = v

print(solve())


### FIXED CODE ###

import numpy as np
from numba import njit


@njit
def solve():
    dp = np.zeros((R + 1, C + 1, 4), dtype=np.int64)
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            for k in range(4):
                dp[i][j][k] = max(dp[i][j - 1][k], dp[i - 1][j][3])
            if items[i][j] == 0:
                continue
            for k in range(3, 0, -1):
                dp[i][j][k] = max(dp[i][j][k], dp[i][j][k - 1] + items[i][j])
    return dp[R][C][-1]


R, C, K, *rcv = map(int, open(0).read().split())

items = np.zeros((R + 1, C + 1), dtype=np.int32)
for r, c, v in zip(*[iter(rcv)] * 3):
    items[r][c] = v

print(solve())
### BUGGY CODE ###

import math
for n in range(1, int(input())+1):
    b=0
    a=[0]*(n+2)
    for i in range(1, n+1):
        if a[i]: continue
        for j in range(1, n+1):
            if a[j]: continue
            # we know z at this point
            d = i + j
            c = n - i**2 - j**2 - i*j
            try:
                k = int(math.sqrt(d**2 + 4*c) - d - 1)
                if k < 1: continue
                if n == (i**2 + j**2 + k**2 + i*j + j*k + i*k):
                    a[i] = True
                    a[j] = True
                    a[k] = True
                    if i == j and i == k and j == k:
                        b+= 1
                    elif i != j and i != k and j !=k:
                        b+=6
                    else:
                        b+=3
            except:
                pass
    print(b)

### FIXED CODE ###

n = int(input())
a = [0]*(n+1)
for i in range(1, 102):
    for j in range(1, 102):
        for k in range(1, 102):
            if (i*i + j*j + k*k + i*j + j*k + i*k) <= n:
                a[i*i + j*j + k*k + i*j + j*k + i*k] +=1
for x in a[1:]:
    print(x)
### BUGGY CODE ###

S = input()
Q = int(input())
T1 = 0
for _ in range(Q):
  a = list(map(str,input().split()))
  if a[0] == '1':
    T1 += 1
  elif a[0] == '2':
    if ((a[1]=='1')and(T1%2==0)) or ((a[1]=='2')and(T1%2!=0)):
      S = a[2]+S
    else:
      S = S+a[2]

if T1 % 2 == 0:
  print(S)
else:
  print(S[::-1])

### FIXED CODE ###

S = input()
Q = int(input())
T1 = 0
S_left = ''
S_right = ''
for _ in range(Q):
  a = list(map(str,input().split()))
  if a[0] == '1':
    T1 += 1
  elif a[0] == '2':
    if ((a[1]=='1')and(T1%2==0)) or ((a[1]=='2')and(T1%2!=0)):
      S_left = a[2]+S_left
    else:
      S_right = S_right+a[2]
S = S_left+S+S_right
if T1 % 2 == 0:
  print(S)
else:
  print(S[::-1])
### BUGGY CODE ###

N, Q = map(int, input().split(' '))
S = input()
queries = tuple(tuple(map(int, input().split(' '))) for _ in range(Q))

ac_indexes = set()
for i in range(N - 1):
    if S[i:i + 2] == 'AC':
        ac_indexes.add(i + 1)

for left, right in queries:
    count = 0
    for i in range(left, right):
        count += int(i in ac_indexes)
    print(count)



### FIXED CODE ###

N, Q = map(int, input().split(' '))
S = input()
queries = tuple(tuple(map(int, input().split(' '))) for _ in range(Q))

cumsum = [0] * (N + 1)
for i in range(N):
    cumsum[i + 1] = cumsum[i]
    if S[i:i + 2] == 'AC':
        cumsum[i + 1] += 1

for left, right in queries:
    print(cumsum[right - 1] - cumsum[left - 1])
### BUGGY CODE ###

def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


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

    c = [0] * (max(a) + 1)
    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from time import time


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    now = time()

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        if time() - now >= 1.8:
            print(n)
            exit()

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()