Problem:


Score : 300 points

Problem Statement

Let f(n) be the number of triples of integers (x,y,z) that satisfy both of the following conditions:

1 \leq x,y,z

x^2 + y^2 + z^2 + xy + yz + zx = n

Given an integer N, find each of f(1),f(2),f(3),\ldots,f(N).

Constraints

All values in input are integers.

1 \leq N \leq 10^4

Input

Input is given from Standard Input in the following format:

N

Output

Print N lines. The i-th line should contain the value f(i).

Sample Input 1

20

Sample Output 1

0
0
0
0
0
1
0
0
0
0
3
0
0
0
0
0
3
3
0
0

For n=6, only (1,1,1) satisfies both of the conditions. Thus, f(6) = 1.

For n=11, three triples, (1,1,2), (1,2,1), and (2,1,1), satisfy both of the conditions. Thus, f(6) = 3.

For n=17, three triples, (1,2,2), (2,1,2), and (2,2,1), satisfy both of the conditions. Thus, f(17) = 3.

For n=18, three triples, (1,1,3), (1,3,1), and (3,1,1), satisfy both of the conditions. Thus, f(18) = 3.



Sample input:
20


Sample output:
0
0
0
0
0
1
0
0
0
0
3
0
0
0
0
0
3
3
0
0

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

n_list = []
for x in range(1, N):
    for y in range(1, N):
        for z in range(1, N):
            cal = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            n_list.append(cal)

for i in range(1, N + 1):
    print(n_list.count(i))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input()) + 1
#Nroot = int(math.sqrt(N/3))+1
for n in range(1,N):
    count = 0
    if n >= 6:
#        print(Nroot, int(math.pow(n,1/3))-1)
        for x in range(int(n/3)+1, int(math.sqrt(n/3))-1 , -1):
            for y in range(x,0,-1):
                if (x+2*y)**2 < n:
                    break
                for z in range(1,y+1):
#                    print((x + y + z)**2 - (x*y + y*z + z*x), n,x,y,z)
#                    print(x,y,z)
                    formula = (x + y + z)**2 - (x*y + y*z + z*x)
                    if formula == n:
                        if x == y and y == z:
                            count += 1
                        else:
                            count += 3
                        break

        print(count)
    else:
        print("0")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = n//2
for l in range(n):
    c = 0
    l += 1
    for i in range(x):
        i += 1
        for j in range(x):
            j += 1
            for k in range(x):
                k += 1
                m = i*i+j*j+k*k+i*j+j*k+k*i
                if m == l:
                    c += 1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
 
for i in range (1,n+1):
  ans=0
  for x in range(1,int(i*2/3)):
   for y in range(1,int(i*2/3)):
    for z in range(1,int(i*2/3)):
     if (x+y+z)**2==i+x*y+x*z+y*z:
       ans+=1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(n,N):
    cnt = 0
    for x in range(1,N):
        for y in range(1, N):
            for z in range(1,N):
                if (((x**2 )+(y**2) +(z**2) +x*y +y*z+ z*x)) == n:
                    cnt += 1

    return cnt
N=int(input())
for i in range(1,N+1):
    print(f(i,N))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
x = 1
for m in range(1,N+1):
  li = int(math.sqrt(m))
  count =0
  y =1
  z =1
  for i in range(li):
    x = i+1
    if 9*x*x >= m:
      for k in range(x):
        y = k+1
        nn = x*x+y*y+x*y
        if nn > m:
          break
        xy = (x+2*y)**2-x*y
        if xy >= m:
          for j in range(y):
            z = j+1
            n = nn+z*z+y*z+z*x
            if n>m:
              break
            if n==m:
              if  x==y or y==z or z==x:
                if x==y and y == z:
                  count =count+1
                else:
                  count = count+3
              else:
                count =count+6
  print(count)

Submission status: Time Limit Exceeded

Solution code:

n=int(input())

def number(i):
   for j in range(1,41):
      for k in range(j,58):
         for u in range(k,101):
            if i==j*j+k*k+u*u+j*k+k*u+u*j:
               if j==k and k==u:
                  print(1)
                  return
               elif j==k or k==u:
                  print(3)
                  return
               else:
                  print(6)
                  return
         

   print(0)
   return

for h in range(1,n+1):
   number(h)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
x = 1
y = 1
z = 1
import math
listN = []
while x<=98:
    y =1
    z =1
    while y<=-x+math.sqrt(-8*(x**2)+120000):
        z = 1
        while z <= 98:
            ans = x**2+y**2+z**2+x*y+y*z+z*x
            if ans<=10000:
                listN.append(ans)
                z = z+1
            else:
                break
        y = y+1
    x = x+1
n = 1
while n<=a:
    print(listN.count(n))
    n = n+1

Submission status: Time Limit Exceeded

Solution code:
import sys


def resolve():
    import math

    readline = sys.stdin.readline

    N = int(readline())

    for i in range(1, N + 1):
        ans = 0
        li = int(math.sqrt(i) // 1)
        for x in range(1, li):
            for y in range(1, li):
                xx = x * x
                yy = y * y
                xy = x * y
                value = (x + y) ** 2 - 4 * (xx + yy + xy - i)
                if value <= 0:
                    continue
                cal = math.sqrt(value)
                z1 = (-(x + y) + cal) / 2
                z2 = (-(x + y) - cal) / 2
                if (1
                        and 1 <= z1
                        and z1 % 1 == 0):
                    ans += 1
                if (1
                        and 1 <= z2
                        and z2 % 1 == 0):
                    ans += 1
        print(ans)


resolve()

Submission status: Time Limit Exceeded

Solution code:
def func(n):
    cnt = 0
    for x in range(1, 33):
        if(x**2+3+2*x > n):
            break
        for y in range(x, 33):
            if(x**2+y**2+x*y+x+y+1 > n):
                break
            for z in range(y, 33):
                if(x**2+y**2+z**2+x*y+y*z+z*x == n):
                    if(x == y == z):
                        cnt += 1
                    elif(x != y and y != z and z != x):
                        cnt += 6
                    else:
                        cnt += 3
                    break
                elif(x**2+y**2+z**2+x*y+y*z+z*x > n):
                    break
        
    return cnt

N = int(input())
    
for i in range(1, N+1):
    print(func(i))

Submission status: Time Limit Exceeded

Solution code:
import math


def pattern(x, y, z):
    if x == y == z:
        return 1
    elif x != y and y != z and x != z:
        return 6
    else:
        return 3


def check(ans):
    cnt = 0
    for x in range(1, ans):
        if pow(x, 2) > ans:
            break
        for y in range(x, ans):
            if pow(x+y, 2) > ans:
                break
            for z in range(y, ans):
                #tmp = x*(x+y+z) + y*(y+z) + z*z
                tmp = pow(x+y+z, 2) - x*(y+z) - y*z
                if tmp == ans:
                    cnt += pattern(x, y, z)
                elif tmp > ans:
                    break
    print(cnt)


N = int(input())
# x^2 + y^2 + z^2 + x*y + y*z + z*x = n

for i in range(1, N+1):
    #upper_value = int(math.sqrt(i))
    check(i)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())

for i in range(1, n+1):
    tmp = 0
    for j in itertools.combinations_with_replacement(range(1, 41), 3):
        x, y, z = j
        if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
            if x == y == z:
                tmp += 1
            elif x != y != z:
                tmp += 6
            else:
                tmp += 3
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input()) 
a = np.zeros((100, 100, 100), dtype=np.int32)
 
 
for i in range(1, 100):
    for j in range(1, 100):
        for k in range(1, 100):
            n = int( ((i+j) * (j+k)) + i*i + k*k)
            a[i,j,k] = n
 
            if n > 1001:
                break
for i in range(N):
    print(np.count_nonzero(a == (i+1)))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())

value_array=[x**2 + y **2 + z ** 2 + x*y + y*z + z*x for x in range(1, int(math.sqrt(N))) for y in range(1, int(math.sqrt(N))) for z in range(1, int(math.sqrt(N)))]
[print(value_array.count(i)) for i in range(1, N+1)]

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
for i in range(1,n+1):
  ans=0
  for x in range(1,int(i**(1/2))):
    for y in range(x,int(i**(1/2))):
      for z in range(y,int(i**(1/2))):
        if (x+y)**2+(y+z)**2+(z+x)**2==2*i:
          if x==y==z:
            ans+=1
          elif (x==y and y!=z) or (x!=y and y==z):
            ans+=3
          elif x!=y and y!=z:
            ans+=6
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
import math
for i in range(1, N+1, 1):
    print(len([[x,y,z] for x in range(1,int(math.sqrt(i+1)),1) for y in range(1,int(math.sqrt(i-x*x)),1) for z in range(1,i-x*x-y*y-x*y,1) if x*x+y*y+z*z+x*y+y*z+z*x == i]))

Submission status: Time Limit Exceeded

Solution code:
import math
 
n=int(input())
 
for i in range (1,n+1):
  ans=0
  for x in range(1,int(i*2/3)):
   for y in range(1,int(i*2/3)):
    for z in range(1,int(i*2/3)):
     if x+y+z==math.sqrt(i+x*y+x*z+y*z):
       ans+=1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())

ans = {}
for v in itertools.combinations_with_replacement(range(1,(N//6)+1), 3):
    x,y,z = v
    count = 0
    if x == y == z:
        fn = 6 * (x**2)
        count = 1
    else:
        fn = x**2 + y**2 + z**2 + x*y + y*z + z*x
        count = 3
    if fn in ans.keys():
        ans[fn] += count
    else:
        ans[fn] = count

for i in range(1,N+1):
    if i in ans.keys():
        print(ans[i])
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
t=int(math.sqrt(n))
for i in range(1,n+1):
  ans=0
  for j in range(1,t):
    for k in range(1,t):
      for l in range(1,t):
        if j**2+k**2+l**2+j*k+k*l+j*l==i:
          ans+=1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def f(n):
    counter = 0
    #print("n=",n)
    for x in range(1,math.floor(math.sqrt(n))+1):
        #print("x=",x)
        for y in range(1,math.floor(math.sqrt(n))+1):
            #print("y=",y)
            for z in range(1,math.floor(math.sqrt(n))+1):
                #print("z=",z)
                if x**2+y**2+z**2+x*y+y*z+x*z == n:
                    counter += 1
    print(counter)

N = int(input())

for n in range(1,N+1):
    f(n)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 0
tmp = []
for i in range(1,58):
    for j in range(1,58):
        for h in range(1,99):
            num = i*i + j*j + h*h + i*j + j*h +h*i
            tmp.append(num)
            num = 0

tmp.sort()


for i in range(1,N+1):
    print(tmp.count(i))

Submission status: Time Limit Exceeded

Solution code:
def tri(n):
    ans = 0
    maxi = 2000
    triger = False
    for i in range(1,int(n**0.5)+1):
        if i > maxi:
            continue
        for j in range(i,int(n**0.5)+1):
            if triger:
                break
            for k in range(i,int(n**0.5)+1):
                if j > k:
                    continue
                if i*i + k*k + j*j + i*k + i*j + j*k == n:
                    if i==k and k==j:
                        ans +=1
                        triger = True
                        break
                    else:
                        ans += 3
                        maxi = max(i,j,k)
                        break
    return ans

N = int(input())

for i in range(1,N+1):
    if i < 6:
        print(0)
        continue
    print(tri(i))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())

a = list(range(N))[1:]
b = list(itertools.combinations_with_replacement(a, 3))
c = [0] * (N + 1)

count = 0

for i in range(len(b)):
    f = b[i][0] ** 2 + b[i][1] ** 2 + b[i][2] ** 2 + b[i][0] * b[i][1] + b[i][1] * b[i][2] + b[i][2] * b[i][0]
    if f <= N:
        c[f] += len(sorted(set(itertools.permutations(b[i]))))

for i in range(1, N + 1):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product

# input = sys.stdin.readline

def ff(N):
#     print("call ff{0}".format(N))
    if N > 100:
        n = int(np.sqrt(20))+5
    else:
        n = N
    cnt = 0
    for x in range(1, n+1):
        x2 = x**2
        for y in range(1, n+1):
            y2 = y**2
            xy = x * y
            tt = x2 + y2 + xy
            if tt > N:
                break
            for z in range(1, n+1):
                num = tt + z**2 + x*z + y*z
                if N == num:
                    cnt += 1
                elif N < num:
                    break
    return(cnt)    
    
N = int(input())    
n = int(np.sqrt(20))+1
for i in range(1, N+1):
#     ff(i)
     print(ff(i))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = [0]*(N+1)
RANGE = 333
for i in range(1, RANGE):
  for j in range(1, RANGE):
    if i**2 + j**2 < N:
      for k in range(1, RANGE):
        wd = i**2 + j**2 + k**2 + i*j + j*k + k*i
        if wd < N:
          #print(wd)
          #print(i, j, k)
          ans[wd] += 1
for i in range(1,N+1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
f = [0] * N
n = math.ceil(math.sqrt(N))

for i in range(1,N+1):
    for x in range(1,i):
        for y in range(x,i):
            for z in range(y,i):
                if(x*x+y*y+z*z+x*y+y*z+z*x == i):
                    if(x == y and y == z) :
                        f[i-1] += 1
                    elif(x == y and y < z):
                        f[i-1] += 3
                    elif(x < y and y == z):
                        f[i-1] += 3
                    else:
                        f[i-1] += 6


[print(a) for a in f]

Submission status: Time Limit Exceeded

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

import sys
import itertools
import math

def input():
    return sys.stdin.readline()


def resolve():
    n = int(input().rstrip())

    for m in range(1, n+1):

        max_n = math.sqrt(n)
        max_n = math.ceil(max_n)
        p = itertools.combinations_with_replacement(range(1,max_n+1), 3)

        ans_cnt = 0
        for v in p:
            #print(v)
            x, y, z = v
            max_value = max(x, y, z)
            min_value = min(x, y, z)
            if min_value*min_value >= m:
                break
            if max_value*max_value >= m:
                continue

            ans = x*x + y*y + z*z + x*y + y*z + z*x

            if ans == m:
                if x == y == z:
                    ans_cnt += 1
                elif x == y or y == z or x == z:
                    ans_cnt += 3
                else:
                    ans_cnt += 6

        print(ans_cnt)



if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import itertools
for i in range(1,n+1):
    a=range(1,n)
    b=range(1,n)
    c=range(1,n)
    res=0
    for x,y,z in itertools.product(a,b,c):
        if x*x+y*y+z*z+x*y+y*z+z*x == i:
            res+=1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
if n<=5:
  for i in range(n):
    print(0)
else:
  for i in range(5):
    print(0)
for i in range(6, n+1):
  count=0
  for x in range(1, int(i/3)):
    if x*x>=i:
      break
    for y in range(1, int(i/3)):
      if y*y>=i:
        break
      for z in range(1, int(i/3)):
        if z*z>=i:
          break
        """print(x,y,z)
        print(x*x + y*y + z*z+ x*y + y*z + z*x)
        print(i)"""
        if x*x + y*y + z*z + x*y + y*z + z*x == i:
          count+=1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
x = 1
for m in range(1,N+1):
  l = math.sqrt(m)
  li = int(l)
  count =0
  y =1
  z =1
  for i in range(li):
    x = i+1
    if 9*x*x >= m:
      for k in range(x):
        y = k+1
        nn = x*x+y*y+x*y
        if nn > m:
          break
        xy = (x+2*y)**2-x*y
        if xy >= m:
          for j in range(y):
            z = j+1
            n = nn+z*z+y*z+z*x
            if n>m:
              break
            if n==m:
              if  x==y or y==z or z==x:
                if x==y and y == z:
                  count =count+1
                else:
                  count = count+3
              else:
                count =count+6
  print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

cnt = 3
for n in range(1, N+1):
    ans = 0
    flg = False
    for i in range(1, cnt-1):
        if flg:
            break
        for j in range(1, cnt-i):
            if flg:
                break
            for l in range(2):
                k = cnt-(i+j)-l
                if (((i+j)**2 + (j+k)**2 + (i+k)**2) == 2*n) and k >= 1:
                    cnt = (i+j+k)+1
                    if i==j and j==k:
                        ans = 1
                    elif i==j or j==k or k==i:
                        ans = 3
                    else:
                        ans = 6
                    flg = True
                    break

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(n):
    if n<2:
        return 0
    lim1 = int((n-2)**0.5-1)+1
    lim2 = int((-2+(4-12*(1-n))**0.5)/6)+1
    lim3 = int(n/6)+1
    
    result=set()
    for x in range(1,lim3):
        for y in range(1,lim2):
            for z in range(1,lim1):
                if x**2+y**2+z**2+x*y+y*z+z*x==n:
                    tmp=set([x,y,z])
                    if tmp not in result:
                        result.add(tuple(tmp))
    
    count=0
    for s in result:
        if len(s)==1:count+=1
        elif len(s)==2:count+=3
        else: count+=6
    return count

for i in range(1,int(input())+1):
    print(f(i))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ans = 0
from itertools import combinations_with_replacement
for i in range(1,n+1):
    ans = 0
    for x,y,z in combinations_with_replacement(range(1,int(i**0.5)), 3):
        #print(i, x,y,z, x**2+y**2+z**2+x*y+y*z+z*x, end=' ')
        if x**2+y**2+z**2+x*y+y*z+z*x == i:
            if x==y==z==x:
                ans +=1
            elif x==y or y==z or z==x:
                ans +=3
            else:
                ans +=6
        #print(ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
for i in range(1,N+1):
  count=0
  k=i//5+1
  for x in range(k):
    if(x==0):
      continue
    if(x>=21):
      break
    for y in range(x,k):
      if(y==0):
        continue
      if(y>=21):
        break
      for z in range(y,k):
        if(z==0):
          continue
        if(z>=21):
          break
        if((x+y)**2+(y+z)**2+(z+x)**2)//2==i:
          #print(x,y,z)
          #print(i)
          if (x==y and y==z and z==x):
            count+=1
          elif (x!=y and y!=z and z!=x):
            count+=6
          else:
            count+=3
  print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr
N = int(input())
for i in range(1, N+1):
    count = 0
    for x, y, z in itr.product(range(1, i), range(1, i), range(1, i)):
        if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == i:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


def f(m):
    ans = 0
    r_m = math.sqrt(m)
    for i in range(1, int(r_m) + 1):
        for j in range(1, int(r_m) + 1):
            for k in range(1, int(r_m) + 1):
                if i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i == m:
                    ans += 1
    return ans


n = I()
for i in range(1, n + 1):
    print(f(i))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

def f(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x

def main():
    N = I()
    ans = 1
    X = 0
    Y = 0
    Z = 0
    XYZ = 0
    arr = []
    dic = {9500: 6, 9501: 6, 9503: 6, 9504: 3, 9505: 6, 9506: 6, 9507: 6, 9508: 6, 9509: 6, 9510: 6, 9511: 6, 9512: 6, 9513: 6, 9514: 6, 9515: 6, 9516: 6, 9517: 6, 9519: 6, 9520: 6, 9521: 6, 9522: 6, 9523: 6, 9524: 6, 9525: 6, 9526: 6, 9527: 6, 9529: 6, 9530: 6, 9531: 6, 9532: 6, 9533: 6, 9535: 6, 9537: 6, 9538: 6, 9539: 6, 9540: 6, 9541: 6, 9542: 6, 9543: 6, 9544: 6, 9545: 6, 9546: 6, 9547: 6, 9548: 6, 9549: 6, 9551: 6, 9552: 6, 9553: 6, 9554: 6, 9555: 6, 9556: 6, 9557: 6, 9558: 6, 9559: 6, 9560: 6, 9561: 6, 9562: 6, 9563: 6, 9564: 6, 9565: 6, 9567: 6, 9568: 6, 9569: 6, 9570: 6, 9571: 6, 9572: 6, 9573: 6, 9574: 6, 9575: 6, 9576: 6, 9577: 6, 9578: 6, 9579: 6, 9580: 6, 9581: 6, 9583: 6, 9584: 6, 9585: 6, 9586: 6, 9587: 6, 9588: 6, 9589: 6, 9590: 6, 9591: 6, 9593: 6, 9594: 6, 9595: 6, 9596: 6, 9597: 6, 9599: 6, 9601: 6, 9602: 6, 9603: 6, 9604: 6, 9605: 6, 9606: 3, 9607: 6, 9608: 3, 9609: 6, 9610: 6, 9611: 6, 9612: 3, 9613: 6, 9615: 6, 9616: 3, 9617: 6, 9618: 6, 9619: 6, 9620: 6, 9621: 6, 9622: 3, 9623: 6, 9624: 6, 9625: 6, 9626: 6, 9627: 6, 9628: 6, 9629: 6, 9631: 6, 9632: 6, 9633: 6, 9634: 6, 9635: 6, 9636: 3, 9637: 6, 9638: 6, 9639: 6, 9640: 6, 9641: 6, 9642: 6, 9643: 6, 9644: 6, 9645: 6, 9647: 6, 9648: 6, 9649: 6, 9650: 3, 9651: 6, 9652: 6, 9653: 6, 9654: 6, 9655: 6, 9657: 6, 9658: 6, 9659: 6, 9660: 6, 9661: 6, 9663: 6, 9665: 6, 9666: 6, 9667: 6, 9668: 6, 9669: 6, 9670: 6, 9671: 6, 9672: 6, 9673: 6, 9674: 6, 9675: 6, 9676: 3, 9677: 6, 9679: 6, 9680: 6, 9681: 6, 9682: 6, 9683: 6, 9684: 6, 9685: 6, 9686: 6, 9687: 6, 9688: 6, 9689: 6, 9690: 6, 9691: 6, 9692: 6, 9693: 6, 9695: 6, 9697: 6, 9698: 6, 9699: 6, 9700: 6, 9701: 6, 9702: 3, 9703: 6, 9704: 6, 9705: 6, 9706: 6, 9707: 6, 9708: 6, 9709: 6, 9711: 6, 9712: 6, 9713: 6, 9714: 6, 9715: 6, 9716: 6, 9717: 6, 9718: 6, 9719: 6, 9721: 6, 9722: 6, 9723: 6, 9724: 6, 9725: 6, 9727: 6, 9728: 3, 9729: 6, 9730: 6, 9731: 6, 9732: 6, 9733: 6, 9734: 6, 9735: 6, 9736: 6, 9737: 6, 9738: 6, 9739: 6, 9740: 6, 9741: 6, 9743: 6, 9744: 6, 9745: 6, 9746: 6, 9747: 6, 9748: 6, 9749: 6, 9750: 6, 9751: 6, 9752: 6, 9753: 6, 9754: 6, 9755: 6, 9756: 6, 9757: 6, 9759: 6, 9760: 6, 9761: 6, 9762: 6, 9763: 6, 9764: 6, 9765: 6, 9766: 6, 9767: 6, 9768: 6, 9769: 6, 9770: 6, 9771: 6, 9772: 6, 9773: 6, 9775: 6, 9776: 6, 9777: 6, 9778: 6, 9779: 6, 9780: 6, 9781: 6, 9782: 6, 9783: 6, 9785: 6, 9786: 6, 9787: 6, 9788: 6, 9789: 6, 9791: 6, 9792: 6, 9793: 6, 9794: 6, 9795: 6, 9796: 6, 9797: 6, 9798: 6, 9799: 6, 9800: 6, 9801: 6, 9802: 6, 9803: 3, 9804: 3, 9805: 6, 9807: 6, 9808: 6, 9809: 3, 9810: 6, 9811: 6, 9812: 6, 9813: 6, 9814: 6, 9815: 6, 9816: 3, 9817: 6, 9818: 6, 9819: 6, 9820: 6, 9821: 6, 9823: 6, 9825: 6, 9826: 6, 9827: 6, 9828: 6, 9829: 6, 9830: 6, 9831: 6, 9832: 6, 9833: 6, 9834: 6, 9835: 6, 9837: 6, 9839: 6, 9840: 6, 9841: 6, 9842: 6, 9843: 6, 9844: 6, 9845: 6, 9846: 6, 9847: 6, 9849: 6, 9850: 6, 9851: 3, 9852: 6, 9853: 6, 9855: 6, 9857: 6, 9858: 6, 9859: 6, 9860: 6, 9861: 6, 9862: 6, 9863: 6, 9864: 6, 9865: 6, 9866: 6, 9867: 6, 9868: 6, 9869: 6, 9871: 6, 9872: 6, 9873: 6, 9874: 6, 9875: 6, 9876: 6, 9877: 6, 9878: 6, 9879: 6, 9880: 6, 9881: 6, 9882: 6, 9883: 6, 9884: 6, 9885: 6, 9887: 6, 9888: 6, 9889: 6, 9890: 6, 9891: 6, 9892: 6, 9893: 6, 9894: 6, 9895: 6, 9896: 6, 9897: 6, 9898: 6, 9899: 3, 9900: 6, 9901: 6, 9903: 6, 9904: 6, 9905: 6, 9906: 6, 9907: 6, 9908: 6, 9909: 6, 9910: 6, 9911: 6, 9913: 6, 9914: 6, 9915: 6, 9916: 6, 9917: 6, 9919: 6, 9921: 6, 9922: 6, 9923: 6, 9924: 6, 9925: 6, 9926: 6, 9927: 6, 9928: 6, 9929: 6, 9930: 6, 9931: 6, 9932: 6, 9933: 6, 9935: 6, 9936: 6, 9937: 6, 9938: 6, 9939: 6, 9940: 6, 9941: 6, 9942: 3, 9943: 6, 9944: 6, 9945: 6, 9946: 6, 9947: 6, 9948: 6, 9949: 6, 9951: 6, 9953: 6, 9954: 6, 9955: 6, 9956: 6, 9957: 6, 9958: 6, 9959: 6, 9960: 6, 9961: 6, 9962: 6, 9963: 6, 9964: 6, 9965: 6, 9967: 6, 9969: 6, 9970: 6, 9971: 6, 9972: 6, 9973: 6, 9974: 6, 9975: 6, 9977: 6, 9978: 6, 9979: 3, 9980: 6, 9981: 6, 9983: 6, 9985: 6, 9986: 6, 9987: 6, 9988: 6, 9989: 6, 9990: 6, 9991: 6, 9992: 6, 9993: 6, 9994: 6, 9995: 6, 9996: 6, 9997: 6, 9999: 6, 10000: 6, 9000: 6, 9001: 6, 9002: 6, 9003: 6, 9004: 6, 9005: 6, 9007: 6, 9008: 3, 9009: 6, 9010: 6, 9011: 6, 9012: 6, 9013: 6, 9014: 6, 9015: 6, 9017: 6, 9018: 6, 9019: 6, 9020: 6, 9021: 6, 9023: 6, 9024: 6, 9025: 6, 9026: 6, 9027: 3, 9028: 6, 9029: 6, 9030: 6, 9031: 6, 9032: 6, 9033: 6, 9034: 6, 9035: 6, 9036: 6, 9037: 6, 9039: 6, 9040: 6, 9041: 6, 9042: 6, 9043: 6, 9044: 6, 9045: 6, 9046: 6, 9047: 6, 9049: 6, 9050: 6, 9051: 6, 9052: 6, 9053: 6, 9055: 6, 9056: 3, 9057: 3, 9058: 6, 9059: 6, 9060: 6, 9061: 6, 9062: 6, 9063: 6, 9064: 6, 9065: 6, 9066: 6, 9067: 6, 9068: 6, 9069: 6, 9071: 6, 9072: 6, 9073: 6, 9074: 6, 9075: 6, 9076: 6, 9077: 6, 9078: 6, 9079: 6, 9081: 3, 9082: 6, 9083: 6, 9084: 6, 9085: 6, 9087: 6, 9089: 6, 9090: 6, 9091: 6, 9092: 6, 9093: 6, 9094: 6, 9095: 6, 9096: 6, 9097: 6, 9098: 6, 9099: 6, 9100: 6, 9101: 6, 9103: 6, 9104: 6, 9105: 6, 9106: 6, 9107: 6, 9108: 6, 9109: 6, 9110: 6, 9111: 6, 9112: 6, 9113: 6, 9114: 6, 9115: 6, 9116: 6, 9117: 6, 9119: 6, 9120: 6, 9121: 6, 9122: 6, 9123: 6, 9124: 6, 9125: 6, 9126: 6, 9127: 6, 9128: 6, 9129: 6, 9130: 6, 9131: 6, 9132: 6, 9133: 6, 9135: 6, 9136: 6, 9137: 6, 9138: 6, 9139: 6, 9140: 6, 9141: 6, 9142: 6, 9143: 6, 9145: 6, 9146: 6, 9147: 6, 9148: 6, 9149: 6, 9151: 6, 9152: 6, 9153: 6, 9154: 6, 9155: 6, 9156: 6, 9157: 6, 9158: 3, 9159: 6, 9160: 6, 9161: 6, 9162: 6, 9163: 6, 9164: 6, 9165: 6, 9167: 6, 9168: 6, 9169: 6, 9170: 6, 9171: 6, 9172: 6, 9173: 6, 9174: 3, 9175: 6, 9176: 6, 9177: 6, 9178: 6, 9179: 6, 9180: 6, 9181: 6, 9183: 6, 9185: 6, 9186: 3, 9187: 6, 9188: 6, 9189: 6, 9190: 6, 9191: 6, 9193: 6, 9194: 6, 9195: 6, 9196: 3, 9197: 6, 9199: 6, 9200: 6, 9201: 6, 9202: 6, 9203: 6, 9204: 6, 9205: 6, 9206: 6, 9207: 6, 9209: 6, 9210: 6, 9211: 6, 9212: 6, 9213: 6, 9215: 6, 9217: 6, 9218: 3, 9219: 6, 9220: 6, 9221: 6, 9222: 6, 9223: 6, 9224: 3, 9225: 6, 9226: 6, 9227: 6, 9228: 6, 9229: 6, 9231: 6, 9232: 6, 9233: 6, 9234: 3, 9235: 6, 9236: 6, 9237: 6, 9238: 6, 9239: 6, 9240: 6, 9241: 6, 9242: 6, 9243: 6, 9244: 6, 9245: 6, 9247: 6, 9248: 3, 9249: 6, 9250: 6, 9251: 6, 9252: 6, 9253: 6, 9254: 6, 9255: 6, 9256: 6, 9257: 6, 9258: 6, 9259: 6, 9260: 6, 9261: 6, 9263: 6, 9264: 6, 9265: 6, 9266: 3, 9267: 6, 9268: 6, 9269: 6, 9270: 6, 9271: 6, 9273: 6, 9274: 6, 9275: 6, 9276: 6, 9277: 6, 9279: 6, 9280: 6, 9281: 6, 9282: 6, 9283: 6, 9284: 6, 9285: 6, 9286: 6, 9287: 6, 9288: 3, 9289: 6, 9290: 6, 9291: 6, 9292: 6, 9293: 6, 9295: 6, 9296: 6, 9297: 6, 9298: 6, 9299: 3, 9300: 6, 9301: 6, 9302: 6, 9303: 6, 9304: 6, 9305: 6, 9306: 6, 9307: 6, 9308: 6, 9309: 6, 9311: 6, 9312: 3, 9313: 6, 9314: 6, 9315: 6, 9316: 6, 9317: 6, 9318: 6, 9319: 6, 9321: 6, 9322: 6, 9323: 6, 9324: 6, 9325: 6, 9327: 6, 9328: 6, 9329: 6, 9330: 6, 9331: 6, 9332: 6, 9333: 6, 9334: 6, 9335: 6, 9337: 6, 9338: 6, 9339: 6, 9340: 6, 9341: 6, 9343: 6, 9344: 3, 9345: 6, 9346: 6, 9347: 6, 9348: 6, 9349: 6, 9350: 6, 9351: 6, 9352: 6, 9353: 6, 9354: 6, 9355: 6, 9356: 3, 9357: 6, 9359: 6, 9360: 6, 9361: 6, 9362: 6, 9363: 6, 9364: 6, 9365: 6, 9366: 6, 9367: 6, 9368: 6, 9369: 6, 9370: 6, 9371: 6, 9372: 6, 9373: 6, 9375: 6, 9376: 6, 9377: 6, 9378: 3, 9379: 6, 9380: 6, 9381: 6, 9382: 6, 9383: 6, 9384: 6, 9385: 6, 9386: 6, 9387: 6, 9388: 6, 9389: 6, 9391: 6, 9392: 6, 9393: 6, 9394: 6, 9395: 6, 9396: 6, 9397: 6, 9398: 6, 9399: 6, 9401: 6, 9402: 6, 9403: 6, 9404: 6, 9405: 6, 9407: 6, 9408: 6, 9409: 6, 9410: 6, 9411: 3, 9412: 6, 9413: 6, 9414: 6, 9415: 6, 9416: 3, 9417: 3, 9418: 6, 9419: 6, 9420: 6, 9421: 6, 9423: 6, 9425: 6, 9426: 6, 9427: 6, 9428: 6, 9429: 6, 9430: 6, 9431: 6, 9432: 6, 9433: 6, 9434: 6, 9435: 6, 9436: 6, 9437: 6, 9439: 6, 9441: 6, 9442: 6, 9443: 6, 9444: 6, 9445: 6, 9446: 6, 9447: 6, 9448: 6, 9449: 6, 9450: 6, 9451: 6, 9452: 6, 9453: 6, 9455: 6, 9456: 6, 9457: 6, 9458: 3, 9459: 3, 9460: 6, 9461: 6, 9462: 6, 9463: 6, 9465: 6, 9466: 6, 9467: 6, 9468: 6, 9469: 6, 9471: 6, 9473: 6, 9474: 6, 9475: 6, 9476: 6, 9477: 6, 9478: 6, 9479: 6, 9480: 6, 9481: 6, 9482: 6, 9483: 6, 9484: 6, 9485: 6, 9487: 6, 9488: 6, 9489: 6, 9490: 6, 9491: 6, 9492: 6, 9493: 6, 9494: 6, 9495: 6, 9496: 6, 9497: 6, 9498: 6, 9499: 6, 9664: 6, 9856: 6}

    for n in range(1, N+1):
        flag = False
        if n in dic:
            print(dic[n])
            continue
        for x in range(1, min(40+1, int(n ** 0.5))):
            for y in range(1, min(57+1, int(n ** 0.5))):
                # for z in range(1, 1):
                if x + y + x > 120:
                    flag = True
                    break
                for z in range(1, min(int(n ** 0.5), 98+1)):
                    if f(x, y, z) == n:
                        flag = True
                        # Z = max(Z, z)
                        # print(n, x, y, z, x + y + z)
                        XYZ = max(XYZ, x + y + z)
                        # if x + y + z >= 100:
                        #     arr.append([n, x, y, z])
                        c = len(set([x, y, z]))
                        if c == 1:
                            print(1)
                            # if n >= 9000:
                            #     dic[n] = 1
                        elif c == 2:
                            print(3)
                            # if n >= 9000:
                            #     dic[n] = 3
                        else:
                            print(6)
                            # if n >= 9000:
                            #     dic[n] = 6
                        # print(n, x, y, z, c)
                    if flag:
                        break
                if flag:
                    break
            if flag:
                break
        if flag == False:
            print(0)

    # print(XYZ)
    # print(arr)
    # print(dic)

if __name__ == '__main__':
    main()