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

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n = int(input())
    a = list(map(int, readline().split()))

    def factorization(n):
        factors = []

        while n % 2 == 0:
            factors.append(2)
            n //= 2

        for i in range(3, int(n ** 0.5) + 5, 2):
            while n % i == 0:
                factors.append(i)
                n //= i
        if n != 1:
            factors.append(n)

        return Counter(factors)

    a_fac = [0] * n

    for i, num in enumerate(a):
        a_fac[i] = factorization(num)

    lcm = {1: 1}

    for fac in a_fac:
        for key, value in fac.items():
            lcm[key] = max(lcm.get(key, 0), value)

    ans = 0

    for fac in a_fac:
        temp = 1
        for key, value in lcm.items():
            p = value - fac.get(key, 0)
            temp *= pow(key, p)
            temp %= MOD
        ans += temp
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n = int(input())
    a = list(map(int, readline().split()))

    def factorization(n):
        factors = []

        while n % 2 == 0:
            factors.append(2)
            n //= 2

        for i in range(3, int(n ** 0.5) + 5, 2):
            while n % i == 0:
                factors.append(i)
                n //= i
        if n != 1:
            factors.append(n)

        return Counter(factors)

    a_fac = [0] * n

    for i, num in enumerate(a):
        a_fac[i] = factorization(num)

    lcm = {1: 1}

    for fac in a_fac:
        for key, value in fac.items():
            lcm[key] = max(lcm.get(key, 0), value)

    ans = 0

    lcmmod = 1

    for key, value in lcm.items():
        lcmmod *= pow(key, value, MOD)
        lcmmod %= MOD

    for ele in a:
        ainv = pow(ele, MOD - 2, MOD)
        ans += ((lcmmod*ainv) % MOD)
        ans %= MOD

    print(ans)


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

import sys
n = int(sys.stdin.readline()[:-1])
S = list(map(int, (sys.stdin.readline()[:-1]).split()))
q = int(sys.stdin.readline()[:-1])
T = list(map(int, (sys.stdin.readline()[:-1]).split()))

def search(A, leng, i):
    if leng == 1:
        return A[0] == i
    half = leng // 2
    h = A[half]
    if h == i:
        return True
    elif h < i:
        return search(A[half:], len(A[half:]), i)
    elif i < h:
        return search(A[:half], len(A[:half]), i)

count = 0
for t in T:
    if search(S, n, t):
        count += 1
print(count)

### FIXED CODE ###

import sys
n = int(sys.stdin.readline()[:-1])
S = [int(x) for x in (sys.stdin.readline()[:-1].split())]
q = int(sys.stdin.readline()[:-1])
T = [int(x) for x in (sys.stdin.readline()[:-1].split())]

count = 0
for t in T:
    l = 0
    h = n - 1
    while l <= h:
        half = (h + l) // 2
        if S[half] == t:
            count += 1
            break
        elif S[half] < t:
            l = half + 1
        else:
            h = half - 1

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

n,a,b = map(int,input().split())
tot = n
count = 0

while tot > 0:
  tot -= a
  if tot > 0:
    count += a
  else:
    count += a+tot
  tot -= b
print(count)

### FIXED CODE ###

import math
n,a,b = map(int,input().split())
hako = a+b
hako_include = math.floor(n/hako)

nokori = n-hako_include*hako
if nokori >= a:
  print(hako_include*a + a)
else:
  print(hako_include*a + nokori)
### BUGGY CODE ###

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

def calc_n(SS):
  cnt=0
  if SS[0]=='R' and SS[1]=='R':
    cnt+=1
  for i in range(1,N-1):
    if SS[i]=='L' and SS[i-1]=='L':
      cnt+=1
    elif SS[i]=='R' and SS[i+1]=='R':
      cnt+=1
  if SS[-1]=='L' and SS[-2]=='L':
    cnt+=1  
  return cnt
  
new_queue=[S]
cnt=0

while(True):  
  cnt+=1
  queue=new_queue[:]

  for q in queue:
    for l in range(N):
      for r in range(l,N):
        new_S = q[0:l]
        for k in range(l,r+1):
          if q[r+l-k]=='L':
            new_S += 'R'
          else:
            new_S += 'L'
        new_S += q[r+1:N]
        new_queue.append(new_S)
        
  if cnt>=K:
    break
    
#print(new_queue)
answer=-1
answer_arg=""
for q in new_queue:
  if calc_n(q)>answer:
    answer=calc_n(q)
    answer_arg=q
    
print(answer)
#print(answer_arg)

### FIXED CODE ###

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

ch_list=[]
for i in range(1,N):
  if S[i-1]!=S[i]:
    ch_list.append(i)
#print(ch_list)
len_ch=len(ch_list)

if len_ch>=2*K:
  print(N-1-len_ch+2*K)
elif len_ch==2*K-1:
  print(N-1-len_ch+2*K-1)
else:
  print(N-1)
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 1e9+7
n, x = map(int, input().split())
s = list(map(int, input().split()))
s.sort(reverse=True)
dp = [[0 for _ in range(x+1)] for _ in range(n+1)]
dp[0][x] = 1
for i in range(n):
	for j in range(x+1):
		dp[i+1][j] += (n-1-i) * dp[i][j]
		dp[i+1][j%s[i]] += dp[i][j]
	for j in range(x+1):
		dp[i+1][j] %= MOD
#print(dp)
ans = 0
for j in range(x+1):
	ans += dp[n][j] * j
	ans %= MOD
print(int(ans))

### FIXED CODE ###

import sys
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

MOD = 1e9+7
n, x = map(int, input().split())
s = list(map(int, input().split()))
s.sort(reverse=True)
dp = defaultdict(int)
dp[x] = 1
for i in range(n):
	ss = s[i]
	dpp = defaultdict(int)
	for key, value in dp.items():
		dpp[key] += (n-1-i) * value
		dpp[key%ss] += value
	for key in dpp.keys():
		dpp[key] %= MOD
	dp = dpp
ans = 0
for key, value in dp.items():
	ans += value * key
	ans %= MOD
print(int(ans))
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a for a in A if a <K]
N = len(A)
dp2 = [1] + [0]*K
dpm = [[0]*(K+1) for _ in range(N+1)]
dpm[0][0] = 1
for i, a in enumerate(A):
    for j in range(K, -1, -1):
        dpm[i+1][j] = dpm[i][max(0, j-a)] + dpm[i][j]
#print(dpm)

r = 0
for i, a in enumerate(A[::-1]):
#    print(i, N-i-1, a)
    for j in range(K, -1, -1):
        # 後ろiこの合計がjのもの
#        print("bb", i, j, K-j-a, K-j)
        if dp2[j] > 0:
            # K-j > x >= K-j-a
            if dpm[N-i-1][max(0, K-j-a)] > dpm[N-i-1][K-j]:
                break
    else:
        r += 1
    for j in range(K-1, 0, -1):
        if j-a>=0:
            dp2[j] = dp2[j] + dp2[j-a]
#        print("aa", i, N-i-1)
print(r)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a for a in A if a <K]
N = len(A)
#dpm = [+1) for _ in range(N+1)]
dpm = [0]*(N+1)
dpm[0] = 1<<(K-1)
for i, a in enumerate(A):
    dpm[i+1] = dpm[i] | (dpm[i] >> a)

r = 0
dp2 = 1
for i, a in enumerate(A[::-1]):
    for j in range(a):
        if dp2 & dpm[N-i-1]:
            break
        dpm[N-i-1] >>= 1
    else:
        r += 1
    dp2 |= dp2<<a
    dp2 &= (1<<K)-1
print(r)
### BUGGY CODE ###

S=list(input())
c=0
while len(S)>1:
    before=len(S)
    for i in range(before-1):
        if S[i]+S[i+1]=="01" or S[i]+S[i+1]=="10":
            c+=2
            #S.pop(i)
            #S.pop(i)
            del S[i:i+2]
            break
    if before==len(S):
        break
print(c)


### FIXED CODE ###

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

N = int(input())
l = []
for i in range(N):
  s = input()
  ls = []
  for j in range(10):
    ls.append(s[j])
  ls.sort()
  l.append(ls)
cnt = 0
for i in range(N):
  for j in range(i+1,N):
    if l[i] == l[j]:
      cnt += 1
print(cnt)

### FIXED CODE ###

import collections
N = int(input())
l = []
for i in range(N):
  s = input()
  ls = []
  for j in range(10):
    ls.append(s[j])
  ls.sort()
  sm = ""
  for j in range(10):
    sm += ls[j]
  l.append(sm)

cnt = 0
c = collections.Counter(l)
for i in c.values():
  cnt += i*(i-1)//2
print(cnt)
### BUGGY CODE ###

import numpy as np
import sys

over = 10**18

n = int(input())
a = list(map(int, input().split()))
ans = 1;
for i in range(n):
  ans = ans * a[i]
  if ans > over:
    ans = -1
if ans < 0:
  print(-1)
else:
  print(ans)
  

### FIXED CODE ###

over = 10**18

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

for i in range(n):
  if a[i] == 0:
    ans = 0
if not ans == 0:
  for i in range(n):
    ans = ans * a[i]
    if ans > over:
      ans = -1
      break
if ans < 0:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

from sys import stdin

s = stdin.readline().rstrip()
li = []

for i in range(len(s)):
    if s[i] == "B":
        li.append(0)
    else:
        li.append(1)
count = 0

while True:
    flag = 0
    for i in range(len(li)-1):
        if li[i] == 0 and li[i+1] == 1:
            li[i],li[i+1] = 1,0
            flag = 1
            count += 1
    if flag == 0:
        print(count)
        exit()

### FIXED CODE ###

from sys import stdin

s = stdin.readline().rstrip()

now = 0
count = 0

for i in range(len(s)):
    if s[i] == "W":
        count += (i-now)
        now += 1

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

import sys
import numpy as np

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

N, K = lr()
N += 1
A = np.array([0] + lr())
A %= K
Acum = A.cumsum()
answer = 0
for i in range(N):
    length = N-1-i
    B = (Acum[i+1:] - Acum[i]) % K - np.arange(1, length+1)
    x = len(B) - np.count_nonzero(B)
    answer += x

print(answer)
# 32

### FIXED CODE ###

import sys
import numpy as np
from collections import defaultdict

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

N, K = lr()
A = np.array([1] + lr())
A = (A-1) % K
N += 1
Acum = (A.cumsum() % K).tolist()
d = defaultdict(int)
answer = 0
for i, x in enumerate(Acum):
    answer += d[x]
    d[x] += 1
    if i >= K-1:
        d[Acum[i-(K-1)]] -= 1

print(answer)
### BUGGY CODE ###

# from collections import deque
from itertools import accumulate
def main():
    n, m, k = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    B = [0] + list(map(int, input().split()))
    X = list(accumulate(A))
    Y = list(accumulate(B))

    cnt = 0
    # Aをi個、Bをj個選ぶ
    for i in range(n + 1):
        for j in range(m + 1):
            #print(i,j,X[i],Y[j])
            if X[i] + Y[j] <= k:
                cnt = max(cnt, i + j)
    print(cnt)



if __name__ == "__main__":
    main()


### FIXED CODE ###

# from collections import deque
import numpy as np
def main():
    n, m, k = map(int, input().split())
    A = np.array([0] + list(map(int, input().split())))
    B = np.array([0] + list(map(int, input().split())))
    X = np.cumsum(A)
    Y = np.cumsum(B)
    # print(P,Q)

    cnt = 0
    j = m
    # Aをi個、Bをj個選ぶ
    for i, x in enumerate(X):
        if x > k:
            break

        while x + Y[j] > k:
            j -= 1
        cnt = max(cnt, i + j)

    print(cnt)

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

import copy
N,K,C= map(int,input().split())
S = input()
T = [n for n, v in enumerate(S) if v == "o"]

a,b=[T[0]],[T[-1]]

for i in range(len(T)):
  if len(a)==K and len(b)==K:
    break
  if len(a)!=K:
    if T[i]-a[-1]>C:
      a.append(T[i])
  if len(b)!=K:
    if b[0]-T[-i-1]>C:
      b.insert(0,T[-i-1])
      
for i in range(K):
  if a[i]==b[i]:
    print(a[i]+1)
  

### FIXED CODE ###

N,K,C= map(int,input().split())
S = input()
T = [n for n, v in enumerate(S) if v == "o"]

a,b=[T[0]],[T[-1]]

for i in range(len(T)):
  if len(a)!=K:
    if T[i]-a[-1]>C:
      a.append(T[i])
  if len(b)!=K:
    if b[-1]-T[-i-1]>C:
      b.append(T[-i-1])
      
for i in range(K):
  if a[i]==b[-i-1]:
    print(a[i]+1)
### BUGGY CODE ###

k = int(input())

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

def gcd3(a, b, c):
    return gcd2(gcd2(a, b), c)

a = 1
b = 1
c = 1
result = 0
while (a <= k):
    b = 1
    while (b <= k):
        c = 1
        while (c <= k):
            result += gcd3(a, b, c)
            c += 1
        b += 1
    a += 1
print(result)

### FIXED CODE ###

k = int(input())
#k = 200

class GCD:
    def __init__(self):
        self.cache = {}
        self.cache3 = {}
    def gcd2(self, a, b):
        a, b = sorted([a, b], reverse=True)
        if (a in self.cache and b in self.cache[a]):
            return self.cache[a][b]
        if (a % b == 0):
            if (a not in self.cache):
                self.cache[a] = {}
            self.cache[a][b] = b
            return b
        return self.gcd2(b, a % b)
    def gcd3(self, a, b, c):
        a, b, c = sorted([a, b, c], reverse=True)
        if (a in self.cache3 and b in self.cache3[a] and c in self.cache3[a][b]):
            return self.cache3[a][b][c]
        if (a not in self.cache3):
            self.cache3[a] = {}
        if (b not in self.cache3[a]):
            self.cache3[a][b] = {}
        result = self.gcd2(self.gcd2(a, c), b)
        self.cache3[a][b][c] = result
        return result

a = 1
b = 1
c = 1
result = 0
client = GCD()
while (a <= k):
    b = a
    while (b <= k):
        interval = client.gcd2(a, b)
        c = b
        while (c <= k):
            if (a == b and b == c):
                result += client.gcd2(interval, c)
            elif(a != b and b != c and a != c):
                result += client.gcd2(interval, c) * 6
            else:
                result += client.gcd2(interval, c) * 3
            c += 1
        b += 1
    a += 1
print(result)
### BUGGY CODE ###

n = int(input())
s = []
ans = 0

for i in range(n):
  s.append(''.join(sorted(input())))

for j in range(0, n):
  for k in range(j+1, n):
    if s[j] == s[k]:
      ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = []
ans = 0

for i in range(n):
  s.append(''.join(sorted(input())))
s.sort()

cnt = 1
for j in range(0, n-1):
  if s[j] == s[j+1]:
    cnt += 1
    if j == n-2:
      ans += cnt*(cnt-1)/2
  else:
    ans += cnt*(cnt-1)/2
    cnt = 1
    
print(int(ans))
### BUGGY CODE ###

n,m=map(int,input().split())
l,r=map(int,input().split())
a=set(range(l,r+1))
for i in range(m-1):
    l,r=map(int,input().split())
    a.intersection_update(range(l,r+1))
print(len(a))


### FIXED CODE ###

n,m=map(int,input().split())
ll,rr=0,n
for i in range(m):
    l,r=map(int,input().split())
    ll=max(l,ll)
    rr=min(r,rr)
print(max(rr-ll+1,0))
### BUGGY CODE ###


N = int(input())

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

dic = {}
ans = 0
lis = [0] * (10**6+1)

for i in range(N):

    if i != N-1 and A[i+1] == A[i]:
        lis[A[i]] = 1
        continue

    j = 1
    flag = True
    while j ** 2 <= A[i]:

        if A[i] % j == 0:
            k = A[i] // j

            if lis[j] > 0:
                flag = False
                break
            if lis[k] > 0:
                flag = False
                break

        j += 1

    if flag:
        ans += 1
    lis[A[i]] = 1

print (ans)


### FIXED CODE ###


def Sieve(n): #n以下の素数全列挙(O(nloglogn)) retは素数が入ってる。divlisはその数字の素因数が一つ入ってる

    ret = []
    divlis = [-1] * (n+1) #何で割ったかのリスト(初期値は-1)
    
    flag = [True] * (n+1)
    flag[0] = False
    flag[1] = False

    ind = 2
    while ind <= n:

        if flag[ind]:
            ret.append(ind)

            ind2 = ind ** 2

            while ind2 <= n:
                flag[ind2] = False
                divlis[ind2] = ind
                ind2 += ind

        ind += 1

    return ret,divlis

N = int(input())

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

ans = 0
lis = [0] * (10**6+1)
tmp,dl = Sieve(10**6+2)

for i in range(N):

    if i != N-1 and A[i+1] == A[i]:
        lis[A[i]] = 1
        continue

    dic = {}
    now = A[i]
    while dl[A[i]] != -1:

        if dl[A[i]] not in dic:
            dic[dl[A[i]]] = 1
        else:
            dic[dl[A[i]]] += 1
        A[i] //= dl[A[i]]

    if A[i] != 1:
        if A[i] not in dic:
            dic[A[i]] = 1
        else:
            dic[A[i]] += 1

    l1 = [1]
    #print (now,dic)
    for i in dic:
        l2 = [i**j for j in range(dic[i]+1)]

        tmp = len(l1)
        for x in range(tmp):
            for y in l2:
                if y != 1:
                    l1.append(l1[x]*y)

    flag = True
    #print (now , l1)
    for i in l1:
        if lis[i] > 0:
            flag = False
            break

    if flag:
        ans += 1
    lis[now] = 1

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

import numpy as np

K = int(input())

gcd1 = np.sum(np.arange(1,K+1))
gcd2 = 0
gcd3 = 0

for a in np.arange(1,K):
    for b in np.arange(a+1,K+1):
        gcd_ab = np.gcd(a,b)
        gcd2 += gcd_ab
        for c in np.arange(b+1,K+1):
            gcd3 += np.gcd(gcd_ab,c)

print(gcd1 + 6*gcd2 + 6*gcd3)

### FIXED CODE ###

from math import gcd
K = int(input())
sum_gcd = [0]*201
ans = 0
 
for i in range(1,K+1):
  for j in range(1,K+1):
    sum_gcd[gcd(i,j)] += 1
for i in range(1,K+1):
  for k in range(1,K+1):
    ans += sum_gcd[i]*gcd(i,k)
 
print(ans)
### BUGGY CODE ###

def main():
    n = input()
    for i in xrange(n):
        X = raw_input()
        Y = raw_input()
        print lcs(X,Y)

def lcs(X,Y):
    m = len(X)
    n = len(Y)
    c = [[0]*(n+1) for i in xrange(m+1)]

    for i in xrange(m):
        for j in xrange(n):
            if X[i] == Y[j]:
                c[i+1][j+1] = c[i][j] + 1
            elif c[i][j+1] >= c[i+1][j]:
                c[i+1][j+1] = c[i][j+1]
            else:
                c[i+1][j+1] = c[i+1][j]
    return c[m][n]
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = input()
    for i in xrange(n):
        X = raw_input()
        Y = raw_input()
        print lcs(X,Y)

def lcs(X,Y):
    m = len(X)
    n = len(Y)
    r1 = [0 for i in xrange(n+1)]
 
    for i in xrange(m):
        r0 = r1[:]
        for j in xrange(n):
            if X[i] == Y[j]:
                r1[j+1] = r0[j] + 1
            elif r0[j+1] < r1[j]:
                r1[j+1] = r1[j]
    return r1[-1]

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

import collections

N = int(input())
a = list(map(int,input().split()))
Q = int(input())

c = collections.Counter(a)

for i in range(Q):
    arr = list(map(int,input().split()))
    B = arr[0]
    C = arr[1]

    if(C not in c):
        c[C] = 0

    c[C] += c[B]
    c[B] = 0

    sum = 0
    for key, cnt in c.items():
        sum += key*cnt

    print(sum)

### FIXED CODE ###

import collections

N = int(input())
a = list(map(int,input().split()))
su = sum(a)

Q = int(input())

c = collections.Counter(a)

for i in range(Q):
    arr = list(map(int,input().split()))
    B = arr[0]
    C = arr[1]

    if(C not in c):
        c[C] = 0

    num_B = c[B] # 配列に含まれるBの個数
    c[B] = 0
    c[C] += num_B
    # c[C] += c[B]
    # del c[B]

    # for key, cnt in c.items():
    #     sum -= items():
    #     sum += key*cnt

    su -= num_B * B # bのやつを減らす
    su += num_B * C # cのやつを増やすitems():

    print(su)
### BUGGY CODE ###

s = raw_input()
k = input()

def solve(s, k, i):
    if i >= len(s):
        # print "over"
        return s
    if i == len(s)-1:
        # print "equal"
        t = ord(s[i])+k
        if t > ord("z"):
            # n = (ord("z") - ord("a") + 1)/(t - ord("z"))
            # t = t - (ord("z")-ord("a"))*n
            while t > ord("z"):
                t -= (ord("z") - ord("a") + 1)
        s = s[:i] + chr(t)
        # print s, k
    elif ord(s[i]) + k > ord("z"):
        # print "carry"
        k = k - ord("z") + ord(s[i]) -1
        s = s[:i] + "a" + s[i+1:]        
        # print s,k
    return solve(s,k,i+1)
    
print solve(s,k,0)

### FIXED CODE ###

s = raw_input()
k = input()
i = 0
while True:
    if i == len(s)-1:
        # print "equal"
        t = ord(s[i])+k
        if t > ord("z"):
            t -= ord("a")
            t %= (ord("z")-ord("a") + 1)
            t += ord("a")
        s = s[:i] + chr(t)
        print s
        exit()
        # print s, k
    elif s[i] != "a" and ord(s[i]) + k > ord("z"):
        # print "carry"
        k = k - ord("z") + ord(s[i]) -1
        s = s[:i] + "a" + s[i+1:]        
        # print s,k
    i += 1
### BUGGY CODE ###

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

count = 0

for i in range(1, N+1):
    # print("i", i)
    cnt = 0
    for j in range(1, i+1):
        # print(i)
        # print(j)
        if lists[i-1] <= lists[j-1]:
            # print("II", i)
            cnt += 1
        else:
            continue
    if cnt == i:
        count += 1

print(count)

### FIXED CODE ###

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

count = 0
ans = 0
for i in range(N):
    if i == 0:
        ans = lists[i]
        count += 1
    else:
        if ans >= lists[i]:
            count += 1
            ans = min(ans, lists[i])
        else:
            ans = min(ans, lists[i])


    # lists_slice = lists[:i+1]
    # lists_min = min(lists_slice)
    # if lists_min >= lists[i]:
    #     count += 1
print(count)
### BUGGY CODE ###

import math
N=int(input())

for i in range(1,N+1):
  n_max=math.ceil(math.sqrt(i))
  n_min=math.floor(math.sqrt(i/6))
  res=0

  for x in range(n_min,n_max+1):
    for y in range(1,x+1):
      for z in range(1,y+1):
        if x*x+y*y+z*z+x*y+y*z+z*x==i:
          if x==y and y==z:
            res+=1
          elif x==y or y==z:
            res+=3
          else:
            res+=6
  print(res)

### FIXED CODE ###

import math
N=int(input())


n_max=math.ceil(math.sqrt(N))
res=[0]*(N+1)

for x in range(1,n_max+1):
  for y in range(1,n_max+1):
    for z in range(1,n_max+1):
      v=x*x+y*y+z*z+x*y+y*z+z*x
      if v <= N:
        res[v]+=1

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

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

from itertools import accumulate

xs = list(accumulate(A)) + [0]

result = 0

for i in range(N):
    for j in range(i, N):
        if (xs[j] - xs[i-1]) % M == 0:
            result += 1

print(result)



### FIXED CODE ###

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

from itertools import accumulate

from collections import defaultdict

ts = defaultdict(int)

ts[0] = 1

t = 0
for a in A:
    t = (t + a) % M
    ts[t] += 1

result = 0

for t in ts:
    result += ts[t] * (ts[t] - 1) // 2

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

N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

mod = 998244353
dp = [0] * N
dp[0] = 1

# O(N)で解く！
# N-1個目のマスまでdp
for i in range(N-1):
  for j in range(K):
    for k in range(X[j][0], X[j][1]+1):
      if 0 <= i + k <= N-1:
        dp[i+k] += dp[i]
        dp[i+k] %= mod
      else: continue

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
 
# dpの高速化 => 累積和によって、O(N)で解く
dp = [0] * N
acc = [0]* (N+1)
dp[0], acc[1] = 1, 1
# acc[0] = 0
# acc[1] = dp[0]
# acc[2] = dp[0] + dp[1]
# acc[n] = dp[0] + dp[1] + dp[n-1]

# dp[0] = acc[1] - acc[0]
# dp[1] = acc[2] - acc[1]
# dp[n-1] = acc[n] - acc[n-1]
mod = 998244353
 
for i in range(1, N):
  # acc[i] = dp[0] + ... + dp[i-1] が既知
  # 貰うdp
  for j in range(K):
    r = i - X[j][0]
    l = i - X[j][1]
    if r < 0: continue
    l = max(l, 0)
      
    dp[i] += acc[r+1] - acc[l] # s = dp[L] + ... + dp[R]
    dp[i] %= mod
  acc[i+1] = acc[i] + dp[i] # acc[i+1] = dp[0] + ... + dp[i]

print(dp[N-1])