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

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

import heapq
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = float('inf')

dists = [INF] * (H*W*4)
dists[(r1*W+c1)*4] = 0
hq = [(r1*W+c1)*4]
heapq.heapify(hq)
while hq:
    v = heapq.heappop(hq)
    cp,d = divmod(v,4)
    cy,x = divmod(cp,W)
    c,y = divmod(cy,H)
    if y==r2 and x==c2:
        print(0--c//K)
        exit()
    for di,(dx,dy) in enumerate(dxy):
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if C[ny][nx] == '@': continue
        if di != d:
            nc = c + (K-c)%K
            if dists[(y*W+x)*4+di] <= nc: continue
            dists[(y*W+x)*4+di] = nc
            heapq.heappush(hq, ((nc*H+y)*W+x)*4+di)
        else:
            if dists[(ny*W+nx)*4+di] <= c+1: continue
            heapq.heappush(hq, (((c+1)*H+ny)*W+nx)*4+di)
print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x]: break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
d = list(map(int,input().split()))
m = int(input())
t = list(map(int,input().split()))

d.sort()
t.sort()

p = 0
for i in range(len(t)):
    for j in range(p,len(d)):
        if(t[i] == d[j]):
            t[i] = 0
            d[j] = 0
            p = j
            break
            
print('YES' if sum(t) == 0 else 'NO')

### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections

n = int(input())
d = list(map(int,input().split()))
m = int(input())
t = list(map(int,input().split()))

dc = collections.Counter(d)
tc = collections.Counter(t)
s = [0 for i in range(len(tc))]
for i,index in enumerate(tc):
    s[i] = dc[index]-tc[index]
    

print('YES' if all(list(map(lambda x : x >= 0 , s))) else 'NO')
### BUGGY CODE ###

H,W=map(int,input().split())
A=[list(input()) for _ in range(H)]   # (i,j) = A[i][j]

import copy

ans=0
while 1:
    if all('.' not in A[i] for i in range(H)):
        break
    else:
        ans+=1

    B=copy.deepcopy(A)
    for i in range(H):
        for j in range(W):
            if A[i][j]=='#':
                if i!=0   and A[i-1][j]=='.': B[i-1][j]='#'
                if i!=H-1 and A[i+1][j]=='.': B[i+1][j]='#'
                if j!=0   and A[i][j-1]=='.': B[i][j-1]='#'
                if j!=W-1 and A[i][j+1]=='.': B[i][j+1]='#'
                B[i][j]='X'

    A=copy.deepcopy(B)

print(ans)

### FIXED CODE ###

import numpy as np
import sys
# 距離K以内にxが居ない
# xからの距離を測る

buf = sys.stdin.buffer
R,C = map(int,buf.readline().split())
black = np.zeros((R+2,C+2),dtype=np.bool)
black[1:-1,1:] = (np.frombuffer(buf.read(R*(C+1)),dtype='S1') == b'#').reshape(R,C+1)

INF = 10 ** 9
dist = np.zeros((R,C),dtype=np.int32)
dist[~black[1:-1,1:-1]] = INF

for n in range(1,R):
  np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(R-2,-1,-1):
  np.minimum(dist[n+1]+1,dist[n],out=dist[n])

for n in range(1,C):
  np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(C-2,-1,-1):
  np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

answer = dist.max()
print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

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

kouho = [[set() for _ in range(w)] for _ in range(h)]

delta = AA[0][0] - BB[0][0]
kouho[0][0].add(delta)
kouho[0][0].add(-delta)
dx = [1, 0]
dy = [0, 1]
for y in range(h):
    for x in range(w):
        for d in range(2):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue
            delta = AA[ny][nx] - BB[ny][nx]
            for num in kouho[y][x]:
                temp = ((h + w - 2) - (ny + nx) + 1) * 80
                if temp >= abs(num + delta):
                    kouho[ny][nx].add(num + delta)
                if temp >= abs(num - delta):
                    kouho[ny][nx].add(num - delta)
ans = 10 ** 10
for a in kouho[h - 1][w - 1]:
    ans = min(ans, abs(a))
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline

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

kouho = [[0] * (w) for _ in range(h)]
delta = abs(AA[0][0] - BB[0][0])
kouho[0][0] |= 1 << delta
for y in range(h):
    for x in range(w):
        nx = x + 1
        ny = y
        if nx < w:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) & 1:
                    temp |= 1 << (delta - i)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp

        nx = x
        ny = y + 1
        if ny < h:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) & 1:
                    temp |= 1 << (delta - i)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp
for i in range(81):
    if (kouho[h - 1][w - 1] >> i) & 1:
        print(i)
        exit()
### BUGGY CODE ###

Q = int(input())
isPrime = [-1 for x in range(100001)]
isPrime[1],isPrime[2] = False,True
for i in range(Q):
    ans = 0
    l,r = map(int,input().split())
    for c in range(l,r+1,2):
        other = (c+1)//2
        if isPrime[c] == -1:
            for j in range(2,int(c**0.5)+1):
                if c % j == 0:
                    isPrime[c] = False
                    break
            else:
                isPrime[c] = True
        if isPrime[other] == -1:
            for j in range(2,int(other**0.5)+1):
                if other % j == 0:
                    isPrime[other] = False
                    break
            else:
                isPrime[other] = True
                
        if isPrime[c] and isPrime[other]:
            ans += 1
    print(ans)
    


### FIXED CODE ###

Q = int(input())
isPrime = [True] * 100001
for p in range(2, 100001):
    if isPrime[p]:
       for i in range(p * p, 100001, p):
           isPrime[i] = False
isPrime[1],isPrime[2] = False,True

like_2017 = [0] * 100002
for i in range(1,100001):
    if isPrime[i] and isPrime[(i+1)//2]:
        like_2017[i] = like_2017[i-1] + 1
    else:
        like_2017[i] = like_2017[i-1]
        
for i in range(Q):
    l,r = map(int,input().split())
    print(like_2017[r] - like_2017[l-1])
### BUGGY CODE ###

n,m = map(int,input().split())
AB = []
ans = [0] * (n-1)

for i in range(m):
    AB.append(list(map(int,input().split())))
    
import collections
que = collections.deque()
que.append(1)
    
while que:
    x = que.popleft()
    
    for i in AB:
        a = i[0]
        b = i[1]
        
        if a == x and ans[b-2] == 0:
            ans[b-2] = x
            que.append(b)
        elif b == x and ans[a-2] == 0:
            ans[a-2] = x
            que.append(a)
            
if 0 in ans:
    print("No")
else:
    print("Yes")
    
    for i in ans:
        print(i)

### FIXED CODE ###

n,m = map(int,input().split())
ans = [-1] * n
edge = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
    
import collections
que = collections.deque()
que.append(0)
    
while que:
    x = que.popleft()
    
    for to in edge[x]:
        if ans[to] == -1:
            ans[to] = x + 1
            que.append(to)
            
if -1 in ans[1:]:
    print("No")
else:
    print("Yes")
    print(*ans[1:],sep="\n")
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline

n = int(input())
a = int(input())

color = [a]
color_min = a

for i in range(1, n):
    a = int(input())
    if color_min >= a:
        bisect.insort_left(color, a)
        color_min = a
    else:
        j = bisect.bisect_left(color, a)
        color.pop(j-1)
        bisect.insort_left(color, a)
        color_min = color[0]

print(len(color))


### FIXED CODE ###

from collections import deque
from bisect import bisect_left

n = int(input())
a = [int(input()) for _ in range(n)]

b = deque([])

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[0]:
            b.appendleft(ai)
        else:
            idx = bisect_left(b, ai)
            b[idx-1] = ai

print(len(b))
### BUGGY CODE ###

N = int(input())
L = []
for i in range(N):
    s = input()
    L.append(sorted(s))
L = sorted(L)
ans = 0
a = 0
for i in range(a,N):
    for j in range(i+1,N):
        if L[i] == L[j]:
            ans += 1
        else:
            a = j
print(ans)

### FIXED CODE ###

import math
N = int(input())
L = []
for i in range(N):
    s = input()
    L.append(sorted(s))
L = sorted(L)
ans = 0
comb = 0
a = 0
b = 1
while b <= N-1:
    if L[a] == L[b] and b-a == 1:
        comb += 2
        b += 1
    elif L[a] == L[b]:
        comb += 1
        b += 1
    elif comb != 0:
        ans += (math.factorial(comb))//((math.factorial(comb-2))*2)
        a = b
        b = a+1
        comb = 0
    else:
        a = b
        b = a + 1
if comb != 0:
    ans += (math.factorial(comb)) // ((math.factorial(comb - 2)) * 2)
print(ans)
### BUGGY CODE ###

import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input=sys.stdin.readline
from random import randint
##import numpy as np
##sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
##def gcd(a,b): 
##    if a == 0: 
##        return b 
##    return gcd(b % a, a) 
def lcm(a,b): 
    return (a*b) // math.gcd(a,b) 
for _ in range(1):
    n=inin()
    l=ain()
    f1,f2=0,0
    gc=lc=l[0]
    for i in range(1,n):
        gc=math.gcd(gc,l[i])
        if(f1==0):
            if(math.gcd(l[i],lc)!=1):f1=1
        if(f1==0):lc=lcm(lc,l[i])
    if(gc!=1):print("not coprime")
    else:
        if(f1):
            print("setwise coprime")
        else:
            print("pairwise coprime")
        
        
    
    
    

 
    
    
    
    
        
        
    
    
    
    


    




##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo


### FIXED CODE ###

import math
N=int(input())
m=10**6+1
M=[0]*m
g=0
for i in map(int,input().split()):M[i]+=1;g=math.gcd(g,i)
if g>1:print('not coprime')
elif all(sum(M[i::i])<=1 for i in range(2,m)):print('pairwise coprime')
else:print('setwise coprime')
### BUGGY CODE ###

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

L=[0]*M
R=[0]*M
for i in range(M):
  L[i], R[i] = map(int, input().split())

common = set(range(1, N+1))
for i in range(M):
  common = common & set(range(L[i],R[i]+1))

print(len(common))

### FIXED CODE ###

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

L=[0]*M
R=[0]*M
for i in range(M):
  L[i], R[i] = map(int, input().split())
    
print(max(min(R)-max(L)+1,0))
### BUGGY CODE ###

import sys

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

if len(H)==1:
    print("Yes")
    sys.exit()
else:
    Flag = [0 for i in range(len(H))]
    x = 0

while x < len(H)-1:

    diff = H[x+1] - H[x]
    if diff < 0:
        if Flag[x]==1:
            print("No")
            sys.exit()
        else:
            Flag[x]=1
            H[x] -= 1
            x=0
            continue
    x += 1
print("Yes")


### FIXED CODE ###

import sys

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

if len(H)==1:
    print("Yes")
    sys.exit()
else:

    Flag = [0 for i in range(len(H))]
    x = 0

while x < len(H)-1:

    diff = H[x+1] - H[x]
    if diff < 0:
        if Flag[x]==1:
            print("No")
            sys.exit()
        else:
            Flag[x]=1
            H[x] -= 1
            x-=1
            continue
    x += 1
print("Yes")
### BUGGY CODE ###

N = int(input())

def count_n(n):
    ans = 0
    for x in range(1,int(N**0.5)+1):
        for y in range(1,int(N**0.5)+1):
            for z in range(1,int(N**0.5)+1):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    ans += 1
    return ans

for i in range(1,N+1):
    print(count_n(i))

### 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 ###

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

ans = 1

for i in range(n):
    ans *= A[i]

if ans > 10**18:
    print("-1")
elif 0 in A:
    print("0")
else:
    print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in A:
    print("0")
    exit()

for i in range(n):
    ans *= A[i]
    if ans > 10**18:
        print("-1")
        exit()

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

import heapq

N, M = map(int, input().split())
A = list(map(lambda x: int(x), input().split()))
heapq.heapify(A)

for i in range(M):
    B, C = map(int, input().split())

    for i in range(B):
        tmp = heapq.heappop(A)
        if tmp < C:
            heapq.heappush(A, C)
        else:
            heapq.heappush(A, tmp)

print(sum(A))



### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(lambda x: int(x), input().split()))
Q = []

for i in range(M):
    Q.append(tuple(map(int, input().split())))

A.sort()

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

cur = 0
for i in range(M):
    cnt = Q[i][0]
    while cnt > 0 and cur < N:
        if A[cur] >= Q[i][1]:
            break
        A[cur] = Q[i][1]
        cur += 1
        cnt -= 1

print(sum(A))
### BUGGY CODE ###

def comb(val):
    if(val > 0):
        return int(val*(val-1) / 2)
    else:
        return 0
    
def make_map(balls):
    balls_map = {}
    for ball in balls:
        if(ball in balls_map):
            balls_map[ball] += 1
        else:
            balls_map[ball] = 1
    return balls_map

def main():
    args = input().rstrip().split(' ')
    N = int(args[0])
    balls = [val for val in input().rstrip().split(' ')]
    balls_map = make_map(balls)
    
    for ball in balls:
        balls_map[ball] -= 1
        sum_ = 0
        for val in balls_map.values():
            sum_ += comb(val)
        print(sum_)
        balls_map[ball] += 1
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def comb(val):
    if(val > 0):
        return int(val*(val-1) / 2)
    else:
        return 0
    
def make_map(balls):
    balls_map = {}
    for ball in balls:
        if(ball in balls_map):
            balls_map[ball] += 1
        else:
            balls_map[ball] = 1
    return balls_map

def main():
    args = input().rstrip().split(' ')
    N = int(args[0])
    balls = [val for val in input().rstrip().split(' ')]
    balls_map = make_map(balls)
    
    sum_ = 0
    for val in balls_map.values():
        sum_ += comb(val)
    for ball in balls:
        print(sum_ - (balls_map[ball]-1))
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    from itertools import accumulate
    S = [i for i in accumulate(range(1, N+1))]

    def is_ok(mid):
        if N <= S[mid]:
            return True
        else:
            return False

    def binary_search_meguru():
        left = -1
        right = N
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(mid):
                right = mid
            else:
                left = mid
        return right

    ans = binary_search_meguru() + 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    from itertools import accumulate
    S = [i for i in accumulate(range(1, min(N+1, 100000)))]

    def is_ok(mid):
        if N <= S[mid]:
            return True
        else:
            return False

    def binary_search_meguru():
        left = -1
        right = len(S)
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(mid):
                right = mid
            else:
                left = mid
        return right

    ans = binary_search_meguru() + 1
    print(ans)


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

h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())

area = []
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        count = 1
        delta = 1
        while j - delta >= 0:
            if s[i][j - delta] == ".":
                count += 1
                delta += 1
            else:
                break
        delta = 1
        while j + delta <= w - 1:
            if s[i][j + delta] == ".":
                count += 1
                delta += 1
            else:
                break
        delta = 1
        while i - delta >= 0:
            if s[i - delta][j] == ".":
                count += 1
                delta += 1
            else:
                break
        delta = 1
        while i + delta <= h - 1:
            if s[i + delta][j] == ".":
                count += 1
                delta += 1
            else:
                break
        area.append(count)
print(max(area))

### FIXED CODE ###

h, w = map(int, input().split())
s = []
s.append(["#"] * (w + 2))
for i in range(h):
    s.append(["#"] + list(input()) + ["#"])
s.append(["#"] * (w + 2))

num = [[-1 for i in range(w + 2)] for i in range(h + 2)]
for i in range(1, h + 1):
    l = 0
    m = 0
    while l < w + 2:
        if s[i][l] == "#":
            l += 1
            continue
        else:
            m = l
            while s[i][m] == ".":
                m += 1
            else:
                for j in range(l, m):
                    num[i][j] += m - l
                l = m
for i in range(1, w + 1):
    l = 0
    m = 0
    while l < h + 2:
        if s[l][i] == "#":
            l += 1
            continue
        else:
            m = l
            while s[m][i] == ".":
                m += 1
            else:
                for j in range(l, m):
                    num[j][i] += m - l
                l = m
print(max([max([num[i][j] for j in range(w + 2)]) for i in range(h + 2)]))
### BUGGY CODE ###

import bisect

A, B, Q = map(int, input().split())
s = [0]*(A+4)
t = [0]*(B+4)

for i in range(2, A+2):
    s[i] = int(input())

for i in range(2, B+2):
    t[i] = int(input())

s[0], s[1], s[-2], s[-1] = -10**11-1, -10**11, 10**11, 10**11+1
t[0], t[1], t[-2], t[-1] = -10**11-1, -10**11, 10**11, 10**11+1


for i in range(Q):
    x = int(input())
    sh_left = bisect.bisect(s, x) - 1
    sh_right = bisect.bisect(s, x)
    ans = 10**12
    for i in range(2):
        loc_sh = s[[sh_left, sh_right][i]]
        dis = abs(x-loc_sh)
        te_left = bisect.bisect(t, loc_sh) - 1
        te_right = bisect.bisect(t, loc_sh)
        loc_te_l = t[te_left]
        loc_te_r = t[te_right]
        tmp = min(dis+abs(loc_sh-loc_te_l), dis+abs(loc_sh-loc_te_r))
        ans = min(ans, tmp)
    te_left = bisect.bisect(t, x) - 1
    te_right = bisect.bisect(t, x)
    for i in range(2):
        loc_te = t[[te_left, te_right][i]]
        dis = abs(x-loc_te)
        sh_left = bisect.bisect(s, loc_te) - 1
        sh_right = bisect.bisect(s, loc_te)
        loc_sh_l = s[sh_left]
        loc_sh_r = s[sh_right]
        tmp = min(dis+abs(loc_te-loc_sh_l), dis+abs(loc_te-loc_sh_r))
        ans = min(ans, tmp)
    print(ans)


### FIXED CODE ###

from bisect import bisect_right

A, B, Q = map(int, input().split())
INF = 10**18
s = [-INF] + [int(input()) for _ in range(A)] + [INF]
t = [-INF] + [int(input()) for _ in range(B)] + [INF]

for _ in range(Q):
    x = int(input())
    sh_r, te_r = bisect_right(s, x), bisect_right(t, x)
    sh_l, te_l = sh_r - 1, te_r - 1
    SR, SL, TR, TL = s[sh_r], s[sh_l], t[te_r], t[te_l]
    ans = INF
    for i in [SR, SL]:
        for j in [TR, TL]:
            dis = abs(i-x) + abs(i-j)
            dis = min(dis, abs(j-x) + abs(j-i))
            ans = min(ans, dis)
    print(ans)
### BUGGY CODE ###

import sys
from math import sqrt
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    for n in range(1, N + 1):
        ans = 0
        upper = 42
        #print("n={}, upper={}".format(n, upper))
        for x in range(1, upper):
            for y in range(1, upper):
                for z in range(1, upper):
                    if (x + y + z)**2 - (x*y + y*z + z*x) == n:
                        ans += 1
        print(ans)



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from math import sqrt
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    for n in range(1, N + 1):
        ans = 0
        #print("n={}".format(n))
        for x in range(1, 41):
            # x==yの時
            if n - 2*x*x >= 0:
                z0 = round(sqrt(n - 2*x*x) - x)
                for z in range(z0 - 2, z0 + 3):
                    if (x + z)**2 + 2*x*x == n:
                        if x == z:
                            #print(x, x, x)
                            ans += 1
                        elif x < z:
                            #print(x, x, z)
                            ans += 3
            # x < y <= zの時
            if n - x**2 >= 0:
                upper = round(sqrt((n - x**2) / 3) - x / 3) + 5
                for y in range(x+1, upper):
                    val = x**2 + x*y + y**2
                    if (x + y)**2 - 4 * (val - n) >= 0:
                        z0 = round((-(x+y) + sqrt((x + y)**2 - 4 * (val - n))) / 2)
                        for z in range(z0-2, z0+3):
                            if z**2 + (x + y)*z + val == n:
                                if y == z:
                                    #print(x, y, z)
                                    ans += 3
                                elif y < z:
                                    #print(x, y, z)
                                    ans += 6
        print(ans)




if __name__ == "__main__":
    main()