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

N=int(input())
L=list(map(int,input().split()))
ans=0
c=[0]*1001
for i in L:c[i]+=1
for i in range(1000):c[i+1]=c[i]+c[i+1]
for i in range(N):
    for j in range(N):
        if i!=j:
            l,r=abs(L[i]-L[j]),min(L[i]+L[j]-1,1000)
            s=c[r]-c[l]
            if l<L[i] and L[i]<=r:s-=1
            if l<L[j] and L[j]<=r:s-=1
            ans+=max(s,0)
print(ans//6)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
ans=0
c=[0]*1001
for i in L:c[i]+=1
for i in range(1000):c[i+1]=c[i]+c[i+1]
for i in range(N-1):
    for j in range(i+1,N):
        l,r=abs(L[i]-L[j]),min(L[i]+L[j]-1,1000)
        ans+=c[r]-c[l]
        if l<L[i] and L[i]<=r:ans-=1
        if l<L[j] and L[j]<=r:ans-=1
print(ans//3)
### BUGGY CODE ###

import numpy as np
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = np.array([10**10]*(n))
dp[0] = 0
if n-1 <= k:
    print(abs(h[-1]-h[0]))
else:
    for i in range(1,k+1):
        dp[i] = abs(h[i]-h[0])
    for i in range(k+1,n): 
        for j in range(1,k+1):
            dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))
    print(dp[-1])

### FIXED CODE ###

import numpy as np
n,k = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.zeros(n, dtype = int)
for i in range(1,n):
    s = max(0,i-k)
    dp[i] = min(dp[s:i] + np.abs(h[i] -h[s:i]))
print(dp[-1])
### BUGGY CODE ###

import bisect

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

Q = int(input())

for i in range(Q):
  x,y = map(int,input().split())
  search = x
  A.sort()
  b=bisect.bisect_left(A,search)
  c=bisect.bisect_right(A,search)
  for j in range(b,c):
    A[j] = y
  print(sum(A))



### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for i in range(Q)]
B, C = [list(i) for i in zip(*BC)]
#print(B,C,BC)

dic = {}
for a in A:
  dic[a] = dic.get(a,0) + 1
#print(dic)

ans = sum(A)
for q in range(Q):
  ans = ans + (C[q]-B[q]) * dic.get(B[q],0)
  dic[C[q]] = dic.get(B[q],0) + dic.get(C[q],0)
  dic[B[q]] = 0
  print(ans)
### BUGGY CODE ###

n, p = list(map(int, input().split(" ")))

if p == 1:
    print(1)
elif n == 1:
    print(p)
else:
    g = 1
    r = 1
    while g**n <= p:
        if p%(g**n) == 0:
            r = g
        g += 1
    print(r)

### FIXED CODE ###

n, p = list(map(int, input().split(" ")))

if p == 1:
    print(1)
elif n == 1:
    print(p)
else:
    for i in range(round(p**(1/n)), 0, -1):
        if p % i**n == 0:
            print(i)
            break
### BUGGY CODE ###

n = input()
line = input()
n = int(n)
a_list = line.split(" ")
a_list = [int(a) for a in a_list]

for i in range(n):
    print(a_list.count(i+1))


### FIXED CODE ###

n = input()
line = input()
n = int(n)
a_list = line.split(" ")
a_list = [int(a) for a in a_list]

ans_list = [0 for i in range(n)]

for a in a_list:
    ans_list[a-1] = ans_list[a-1] + 1

for ans in ans_list:
    print(ans)
### BUGGY CODE ###

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

dp=[[[0 for i in range(0,2)] for j in range(0,N+2)] for k in range(0,N+1)]

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


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

print(dp[0][N+1][0])

### FIXED CODE ###

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


dpx=[[0 for j in range(0,N+2)] for k in range(0,N+1)]
dpy=[[0 for j in range(0,N+2)] for k in range(0,N+1)]

for i in range(0,N+2):
    dpx[N-1][i]=abs(A[N-1]-A[i])
    dpy[N-1][i]=abs(A[N-1]-A[i])


for i in range(1,N):
    for j in range(0,N+2):
        I=N-1-i
        dpx[I][j]=max(dpy[I+1][I],dpx[I+1][j],abs(A[N-1]-A[j]))
        dpy[I][j]=min(dpx[I+1][I],dpy[I+1][j],abs(A[N-1]-A[j]))

print(dpx[0][N+1])
### BUGGY CODE ###

K, S = map(int, input().split())

l = []

for i in range(K + 1):
    l.append(i)

count = 0

for i in l:
    x = i
    for j in l:
        y = j
        for k in l:
            z = k
            if (x + y + z) == S:
                count += 1

print(count)


### FIXED CODE ###

K, S = map(int, input().split())

l = []

for i in range(K + 1):
    l.append(i)

count = 0

for i in l:
    for j in l:
        z = S - i - j
        if 0 <= z and z <= K:
            count += 1

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

N = int(input())


def binary_search(L, target):
    """
    >>> binary_search([1,3,5],2)
    2
    >>> binary_search([1,3,5],5)
    0
    >>> binary_search([1,3,5],9)
    0
    >>> binary_search([1,3,3,3,3,5],3)
    1
    >>> binary_search([1,3,3,3,3,5],4)
    1
    """
    if L[0] > target:
        return len(L)
    if L[-1] <= target:
        return 0
    right_i = len(L) - 1
    left_i = 0
    j = 0
    while left_i + 1 != right_i:
        med_i = (right_i + left_i) // 2
        if L[med_i] < target:
            left_i = med_i
        elif L[med_i] > target:
            right_i = med_i
        else:
            while L[med_i + 1] == target:
                med_i += 1
            return len(L) - med_i - 1
    return len(L) - right_i


D = []
for _ in range(3):
    D.append(list(map(int, input().split())))
A, B, C = D
A = [-a for a in A]
A.sort()
C.sort()
ans = 0

for b in B:
    ans += binary_search(A, -b) * binary_search(C, b)

print(ans)


### FIXED CODE ###

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


def hoge():
    count = 0
    Ai = -1
    Ci = -1
    for i in range(N):
        if Ai < N - 1:
            while A[Ai + 1] < B[i]:
                Ai += 1
                if Ai == N - 1:
                    break
        if Ci < N - 1:
            while C[Ci + 1] <= B[i]:
                Ci += 1
                if Ci == N - 1:
                    break
        count += (Ai + 1) * (N - (Ci + 1))
    return count


print(hoge())
### BUGGY CODE ###

h,w,m = map(int,input().split())
hw = [list(map(int,input().split()))for _ in range(m)]

tate = [0]*(h+1)
yoko = [0]*(w+1)
bombpoint = []

for x,y in hw:
    tate[x] += 1
    yoko[y] += 1
    bombpoint.append((x,y))

ans_x = set()
ans_y = set()
x_max = max(tate)
y_max = max(yoko)
for i in range(len(tate)):
    if tate[i] == x_max:
        ans_x.add(i)
for i in range(len(yoko)):
    if yoko[i] == y_max:
        ans_y.add(i)

ans = x_max + y_max
for x in ans_x:
    for y in ans_y:
        if (x,y) not in bombpoint:
            print(ans)
            exit()
print(ans - 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
h,w,m = map(int,input().rstrip().split())
hw = [list(map(int,input().rstrip().split()))for _ in range(m)]

tate = [0]*(h+1)
yoko = [0]*(w+1)
bombpoint = set()

for x,y in hw:
    tate[x] += 1
    yoko[y] += 1
    bombpoint.add((x,y))

ans_x = []
ans_y = []
x_max = max(tate)
y_max = max(yoko)
for i in range(len(tate)):
    if tate[i] == x_max:
        ans_x.append(i)
for i in range(len(yoko)):
    if yoko[i] == y_max:
        ans_y.append(i)

ans = x_max + y_max
for x in ans_x:
    for y in ans_y:
        if (x,y) not in bombpoint:
            print(ans)
            exit()
print(ans - 1)
### BUGGY CODE ###

N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#######################
# 開始
p_list = XY[:]

# y座標の圧縮
from operator import itemgetter
p_list = sorted(p_list, key=itemgetter(1))
p_list = [ (x, y, i+1) for i, (x, y) in enumerate(p_list)]

# xでソート
p_list= sorted(p_list)

a = [0] * N # 左下
b = [0] * N# 左上
c = [0] * N# 右下
d = [0] * N# 右上

# a,bを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(p_list):
    tmp = bit.sum(r)
    a[i] = tmp
    b[i] = i-tmp
    bit.add(r, 1)

# c,dを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(reversed(p_list)):
    tmp = bit.sum(r)
    c[i] = tmp
    d[i] = i-tmp
    bit.add(r, 1)
c = c[::-1]
d = d[::-1]

# ある点が四角に含まれる場合の総数を求めるメソッド
power = [1] * N
for i in range(1, N):
    power[i] = power[i-1] * 2 % 998244353
 
ans = 0
for i in range(N):
    _a = power[a[i]] - 1
    _b = power[b[i]] - 1
    _c = power[c[i]] - 1
    _d = power[d[i]] - 1
    
    ret = (_a+1) * (_d+1) * _c * _b
    ret += (_b+1) * (_c+1) * _a * _d
    ret -= _a*_b*_c*_d
    ret += power[N-1]
    ans += ret % 998244353
    
print(ans % 998244353)   


### FIXED CODE ###

N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#######################
# 開始
from operator import itemgetter
def solve():
    p_list = XY[:]

    # y座標の圧縮
    p_list = sorted(p_list, key=itemgetter(1))
    p_list = [ (x, y, i+1) for i, (x, y) in enumerate(p_list)]

    # xでソート
    p_list= sorted(p_list)

    # ある点が四角に含まれる場合の総数を求めるメソッド
    power = [1] * N
    for i in range(1, N):
        power[i] = power[i-1] * 2 % 998244353

    # a,bを求める
    bit = Bit(N)
    ans = 0
    for i, (x, y, r) in enumerate(p_list):
        tmp = bit.sum(r)
        a = tmp
        b = i-tmp
        c = r-tmp-1
        d = (N-r+1)-(i-tmp)-1
        bit.add(r, 1)
        _a = power[a] - 1
        _b = power[b] - 1
        _c = power[c] - 1
        _d = power[d] - 1

        ret = (_a+1) * (_d+1) * _c * _b
        ret += (_b+1) * (_c+1) * _a * _d
        ret -= _a*_b*_c*_d
        ret += power[N-1]
        ans += ret % 998244353

    print(ans % 998244353)
    
solve()
### BUGGY CODE ###

a,b=map(int,input().split())
ans=1
for i in range(a,b+1):
  ans*=i
if ans>0:
  print('Positive')
elif ans<0:
  print('Negative')
else:
  print('Zero')


### FIXED CODE ###

a,b=map(int,input().split())
if a*b<=0:
  print("Zero")
elif a>0 or a==b:
  print("Positive")
else:
  if abs(a-b) % 2 == 0:
    print("Negative")
  else:
    print("Positive")
### BUGGY CODE ###

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

# In[27]:


import numpy as np
H, W = map(int, input().split())
S = np.array([list(input()) for i in range(H)])
"""
4 6
#..#..
.....#
....#.
#.#...
"""


# In[47]:


row_beam = np.zeros((H, W))
col_beam = np.zeros((H, W))


# In[48]:


for i in range(H):
    #print(i)
    #print(row_beam)
    row = S[i]
    sharp_pos = np.where(row=='#')[0]
    #print(sharp_pos)
    if len(sharp_pos) == 0:
        row_beam[i] = W
    else:
        s = 0
        for sp in sharp_pos:
            contin = sp-s
            row_beam[i, s:sp] = contin
            s = sp+1
        if s != W:
            row_beam[i, s:W] = W-s
            
for i in range(W):
    #print(i)
    #print(col_beam)
    col = S[:,i]
    sharp_pos = np.where(col=='#')[0]
    #print(sharp_pos)
    if len(sharp_pos) == 0:
        col_beam[:, i] = H
    else:
        s = 0
        for sp in sharp_pos:
            contin = sp-s
            col_beam[s:sp, i] = contin
            s = sp+1
        if s != W:
            col_beam[s:H, i] = H-s


# In[49]:


print(int(np.max(row_beam+col_beam-1)))


# In[ ]:






### FIXED CODE ###

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

# In[76]:


import numpy as np
H, W = map(int, input().split())
S = np.array([list(input()) for i in range(H)])
"""
8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#
"""


# In[84]:


field = np.ones((H, W))
field[S=='#'] = 0
lm, rm, um, dm = (field.copy() for _ in [0]*4)
#print(field)
#print(lm)
#print(rm)
#print(um)
#print(dm)


# In[87]:


#np.where()
for i in range(1, H):
    um[i] = (um[i-1]+1) * field[i]
    dm[-1-i] = (dm[-i]+1) * field[-1-i]
    
for i in range(1, W):
    lm[:, i] = (lm[:, i-1]+1) * field[:, i]
    rm[:, -1-i] = (rm[:, -i]+1) * field[:, -1-i]
    #print(rm)


# In[88]:


#print(field)
#print(um)
#print(dm)
#print(lm)
#print(rm)
print(int(np.max(um+dm+lm+rm)-3))


# In[ ]:
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            p = 0
            for f in range(n):
                if p == 0 and s[f] == str(i):
                    p = 1
                elif p == 1 and s[f] == str(j):
                    p = 2
                elif p == 2 and s[f] == str(k):
                    ans += 1
                    break
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            p=0
            for f in range(n):
                if p == 0 and s[f] == str(i):
                    p = 1
                elif p == 1 and s[f] == str(j):
                    p = 2
                elif p == 2 and s[f] == str(k):
                    ans += 1
                    break
print(ans)
### BUGGY CODE ###

from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
from functools import reduce

n = int(input())
xy = [[i] + list(map(int,input().split())) for i in range(n)]

xy.sort(key=lambda x:x[1])
edge  = []
for i in range(n-1):
    i1,x1,y1 = xy[i]
    i2,x2,y2 = xy[i+1]
    edge.append((x2-x1,i1,i2))

xy.sort(key=lambda x:x[2])
for i in range(n-1):
    i1,x1,y1 = xy[i]
    i2,x2,y2 = xy[i+1]
    edge.append((y2-y1,i1,i2))
class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def size(self, x):
        x = self.find(x)
        return self.counter[x]

    def same(self, x, y):
        return self.find(x) == self.find(y)

#クラスカル法
uf = UnionFind(n+1)
edge.sort()
ans = 0
for c,i1,i2 in edge:
    if uf.same(i1,i2):
        continue
    else:
        uf.unite(i1,i2)
        ans += c
print(ans)

### FIXED CODE ###

n = int(input())
xy = [[i] + list(map(int,input().split())) for i in range(n)]

xy.sort(key=lambda x:x[1])
edge  = []
for i in range(n-1):
    i1,x1,y1 = xy[i]
    i2,x2,y2 = xy[i+1]
    edge.append((x2-x1,i1,i2))

xy.sort(key=lambda x:x[2])
for i in range(n-1):
    i1,x1,y1 = xy[i]
    i2,x2,y2 = xy[i+1]
    edge.append((y2-y1,i1,i2))
class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def size(self, x):
        x = self.find(x)
        return self.counter[x]

    def same(self, x, y):
        return self.find(x) == self.find(y)

#クラスカル法
uf = UnionFind(n)
edge.sort()
ans = 0
edge_cnt = 0
i = 0
while edge_cnt < n-1:
    cost,i1,i2 = edge[i]
    if not uf.same(i1,i2):
        ans += cost
        uf.unite(i1,i2)
        edge_cnt += 1
    i += 1
print(ans)
### BUGGY CODE ###

def primes(n):
    l= []
    for i in range(2,n):
        while n % i == 0:
            n = n//i
            l.append(i)
        if n == 1: 
            break
    
    if n > 1:
        l.append(n)
    return l

a,b=map(int,input().split())
sa=set(primes(a))
sb=set(primes(b))
sans=sa.intersection(sb)
print(len(sans)+1)

### FIXED CODE ###

def primes(n):
    i = 2
    factors = []
    while i**2<= n:
        if n % i:
            i += 1
        else:
            n =n//i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
a,b=map(int,input().split())
sa=set(primes(a))
sb=set(primes(b))
sans=sa.intersection(sb)
print(len(sans)+1)
### BUGGY CODE ###

k = int(input())
n = 7
c = 1
while True:
  tmp = n % k
  if tmp == 0:
    print(c)
    break
  else:
    n = tmp * 10 + 7
    c += 1

### FIXED CODE ###

k = int(input())
n = 7
c = 1
f = 1
if k % 2 == 0:
  print(-1)
else:
  while c < 1000000:
    tmp = n % k
    if tmp == 0:
      print(c)
      f = 0
      break
    else:
      n = tmp * 10 + 7
      c += 1
  if f == 1:
    print(-1)
### BUGGY CODE ###

L, R = map(int, input().split())

M = []
for i in range(L, R+1):
  i2 = i % 2019
  for j in range(i+1, R+1):
    M.append( i2 * (j % 2019) % 2019)
if len(M) == 0:
  print(L)
elif L < 0 and R > 0:
  print (0)
else:
  print (min(M))

### FIXED CODE ###

L, R = map(int, input().split())
if R-L >= 2019:
  print (0)
else:
  print (min([((i % 2019) * (j % 2019)) % 2019 for i in range(L,R) for j in range(i+1,R+1)]))
### BUGGY CODE ###

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

a = len(A)
for i in range(M):
    B,C = map(int, input().split())
    A += [C]*B

A.sort(reverse=True)
print(sum(A[:a]))

### FIXED CODE ###

N, M = map(int,input().split())
A = [[1,int(a)] for a in input().split()]
BC = A + [list(map(int,input().split())) for _ in range(M)]

BC.sort(key=lambda x:x[1], reverse=True)

i = 0
ans = 0
for B,C in BC:
    if i + B <= N:
        ans += B*C
        i += B
    else:
        ans += (N - i) * C
        break

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

import sys,itertools
input = sys.stdin.readline
N = int(input().strip())
S = input().strip()

master = []
for i in range(N):
    existed = False
    for j in itertools.combinations(S,i+1):
        for a in j:
            if j.count(a) > 1:
                existed=True
                break
        if existed:
            existed = False
            continue
        master.append(j)
print(len(master)%((10**9)+7))

### FIXED CODE ###

import sys,itertools
input = sys.stdin.readline
N = int(input().strip())
S = input().strip()

le = [S.count(s)+1 for s in set(S)]
cnt=1
for i in le:
    cnt*=i
print((cnt-1)%((10**9)+7))
### BUGGY CODE ###

#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

    alphabets = [chr(i) for i in range(ord("a"), ord("a")+26)]

    L = {x:[] for x in alphabets} # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。
    for idx, s in enumerate(S):
        L[s].append(idx)

    queries = []
    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            queries.append([int(row[0]), int(row[1])-1, row[2]])
        elif row[0] == '2':
            queries.append([int(row[0]), int(row[1])-1, int(row[2])-1])

    for query in queries:
        if query[0] == 1:
            target = S[query[1]]
            idx_del = bisect.bisect_left(L[target], query[1])
            if idx_del < len(L[target]):
                del L[target][idx_del]
            bisect.insort(L[query[2]], query[1])
            S[query[1]] = query[2]
        elif query[0] == 2:
            answer = 0
            for i in range(26):
                alphabet = chr(ord("a") + i)
                left = bisect.bisect_left(L[alphabet], query[1])
                if left < len(L[alphabet]) and query[1] <= L[alphabet][left] <= query[2]:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

    L = [[] for x in range(26)] # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。

    for idx, s in enumerate(S):
        L[ord(s)-ord("a")].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            y, z = int(row[1])-1, row[2]
            if S[y] != z:
                idx_target = ord(S[y]) - ord("a")
                idx_del = bisect.bisect_left(L[idx_target], y)
                if idx_del < len(L[idx_target]):
                    L[idx_target].pop(idx_del)
                bisect.insort(L[ord(z) - ord("a")], y)
                S[y] = z

        elif row[0] == '2':
            y, z = int(row[1]) - 1, int(row[2]) - 1
            answer = 0
            for idx_alphabet in range(26):
                left = bisect.bisect_left(L[idx_alphabet], y)
                if left < len(L[idx_alphabet]) and y <= L[idx_alphabet][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

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

import random
from copy import deepcopy

random.seed(12345)

N = int(raw_input().split()[0])
inp = map(int, raw_input().split())

health = {}
for k, v in enumerate(inp):
  health[k] = v


l = len(health.keys())
while l > 1:
  available = health.keys()
  
  remaining = deepcopy(health.keys())

  attacker = random.choice(available)
  remaining.remove(attacker)
  defender = random.choice(remaining)

  rem_health = health[defender] - health[attacker]

  if rem_health == 0:
    health.pop(defender, None)
    l -= 1
  elif rem_health < 0:
  	continue

  else:
  	health[defender] = rem_health

print health.values()[0]

### FIXED CODE ###

N = int(raw_input())
health = map(int, raw_input().strip().split())

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

if len(health) == 1:
	print health[0]
else:
	g = gcd(health[0], health[1])
	for i in range(2, len(health)):
		g = gcd(g, health[i])
print g
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input())
for i in range(1,N+1):
  cnt=0
  listx=list(range(1,i-2))
  for x in listx:
    for y in range(1,i-x+1):
      for z in range(1,i-x-y+1):
        if i==x**2+y**2+z**2+x*y+y*z+z*x:
          cnt+=1
  print(cnt)

      

### FIXED CODE ###

import sys
input = sys.stdin.readline
import math

N=int(input())
ans=[0]*(N+1)
sn=int(math.sqrt(N)+1)
for x in range(1,sn+1):
  for y in range(1,sn+1):
    for z in range(1,sn+1):
      i=x**2+y**2+z**2+x*y+y*z+z*x
      if 1<=i<=N:
        ans[i]+=1
for h in range(1,N+1):          
  print(ans[h])