from itertools import combinations_with_replacement
from collections import defaultdict
def g(a,b,c):
    i=0
    while True:
        yield 2*(a*b+b*c+c*a)+4*i*(a+b+c)+4*i*(i-1)
        i=i+1
def f(n):
    M=1000
    Re=defaultdict(int)
    for i in combinations_with_replacement(range(1,100),3):
        N=g(*i)
        v=next(N)
        while v<M:
            if v==154:
                print(i)
            Re[v]+=1
            v=next(N)
    return min(i for i in Re if Re[i]==n);
##print(f(10))

from collections import Counter
def S(T):
    l=[]
    for a in range(1,T//2):
        for b in range(1,min(a+1,(T+1)//(a+1))):
            for c in range(1,min(b+1,(T-a*b+a+b)//(a+b))):
                if a*b+b*c+a*c<=10000:
                    l.append((a+b+c,(a*b+b*c+a*c)))
    return Counter(l)
PS=S(10000)
Eq3=lambda x:(x-1)//3+1
def issquare(x):
    t=int(x**0.5)
    if t*t==x:
        return True,t
    else:
        return False,None
def P3(SUM,SUM2):
    '''a+b+c=SUM,a*b+b*c+a*c=SUM2'''
##    for a in range(Eq3(SUM),SUM-1):
##        isP2,b,c=P2(SUM-a,SUM2+a*a-a*SUM)
####        print(isP2,a,b,c)
##        if isP2 and 0<b<=a and 0<c<=a:
##            yield a,b,c
    if (SUM,SUM2) in PS:
        return PS[(SUM,SUM2)]
    else:
        return 0
def P2(SUM,SUM2):
    '''a+b=SUM,a*b=SUM2'''
    S=SUM**2-4*SUM2
    if S<0:
        return False,None,None
    issq,sq=issquare(S)
    if not issq or (SUM-sq)%2!=0 or SUM<=sq:
        return False,None,None
    else:
        return True,(sq+SUM)//2,(SUM-sq)//2
def Q(SUM2):
    '''a*b+b*c+a*c=SUM2'''
##    print(SUM2,Eq3(SUM2),int(Eq3(SUM2)**0.5),(SUM2-1)//2+1)
    for a in range(int(Eq3(SUM2)**0.5),(SUM2-1)//2+1):
##        print(a,(SUM2-a)//(a+1)+2)
        for S2 in range(2,(SUM2-a)//(a+1)+2):
            isP2,b,c=P2(S2,SUM2-a*S2)
##            print(S2,SUM2-a*S2,isP2,b,c)
            if isP2 and 0<b<=a and 0<c<=a:
                yield a,b,c
def C(SUM):
    '''2*i*i+2*i*(a+b+c-1)+a*b+b*c+a*c=SUM'''
    re=len(list(Q(SUM)))#i=0
    i=1
    while 2*i*i+4*i+3<=SUM:
        T=SUM-2*i*(i-1)
        #int((9*i*i+3*T)**0.5)-3*i
        for S3 in range(int((9*i*i+3*T)**0.5)-3*i,(T+4*i-1)//(2*i+2)+1):
##            re+=len(list(P3(S3,T-2*i*S3)))
            re+=P3(S3,T-2*i*S3)
        i+=1
    return re
def test(m):
    for a,b,c in Q(m):
        print(a,b,c)
def f2(n):
    i=0
    while True:
        if i%100==0:
            print(i,C(i))
        if C(i)==n:
            return 2*i
        i+=1
##print(f2(10))
from timeit import Timer
def test():
    print(f2(1000))
t=Timer("test()","from __main__ import test")
print(t.timeit(1))
