import functools
import time
@functools.lru_cache(maxsize=None)
def stevilo_enic_rekurzija(stevilo):
    '''
        rekurzivna rešitev, ki vrne najmanjše število enic,
        ki jih potrebujemo, da z naborom znakov {+,*,(,),1}
        dobimo aritmetični izraz, katerega vrednost je enak številu 'stevilo'
    '''
    if stevilo == 1:
        return 1
    vsota = min([stevilo_enic_rekurzija(stevilo - i) + stevilo_enic_rekurzija(i) for i in range(1,int(stevilo // 2) + 1)])
    try:
        zmnozek = min([stevilo_enic_rekurzija(stevilo / i) + stevilo_enic_rekurzija(i) for  i in range(2,int(stevilo**(1/2)) +1) if stevilo / i == stevilo // i ])
    except:
        return vsota
    return min(vsota,zmnozek)



def stevilo_enic_dinamicna(stevilo):
    '''
        dinamična rešitev, ki vrne najmanjše število enic,
        ki jih potrebujemo, da z naborom znakov {+,*,(,),1}
        dobimo aritmetični izraz, katerega vrednost je enak številu 'stevilo'
    '''
    if stevilo < 1:
        raise Exception('Tole pa ne bo šlo')
    tabela = [float('inf')]*(stevilo +1)
    tabela[0] = 0
    tabela[1] = 1
    for st in range(2,stevilo+1):
        #vsote
        koren = st**(1/2)
        for i in range(1,st // 2 + 1):
            tabela[st] = min(tabela[st],tabela[i] + tabela[st -i])
            if i <= koren:
                if st / i == st // i:#vsota je deljiva s številom 
                    tabela[st] = min(tabela[st],tabela[i] + tabela[int(st/i)])
    return tabela[-1]

if False:
    cas1 = time.time()
    stevilo_enic_dinamicna(500)
    cas2 = time.time()
    print(cas2-cas1)

    cas1 = time.time()
    stevilo_enic_dinamicna(1000)
    cas2 = time.time()
    print(cas2-cas1)


    cas1 = time.time()
    stevilo_enic_dinamicna(2000)
    cas2 = time.time()
    print(cas2-cas1)



    cas1 = time.time()
    stevilo_enic_dinamicna(4000)
    cas2 = time.time()
    print(cas2-cas1)

    cas1 = time.time()
    stevilo_enic_dinamicna(8000)
    cas2 = time.time()
    print(cas2-cas1)
    
    
    
def stevilo_enic_izpisi_izraz(stevilo):
    '''
        dinamična rešitev, ki vrne najmanjše število enic,
        ki jih potrebujemo, da z naborom znakov {+,*,(,),1}
        dobimo aritmetični izraz, katerega vrednost je enak številu 'stevilo'
    '''
    if stevilo < 1:
        raise Exception('Tole pa ne bo šlo')
    tabela = [float('inf')]*(stevilo +1)
    tabela_zapis = [1]*(stevilo +1)
    tabela_zapis[1] = 1
    tabela[0] = 0
    tabela[1] = 1
    for st in range(2,stevilo+1):
        #vsote
        koren = st**(1/2)
        for i in range(1,st // 2 + 1):
            if tabela[i] + tabela[st -i] < tabela[st]:
                tabela[st] = tabela[i] + tabela[st -i]
                tabela_zapis[st] = (i,'+',st-i)

            if i <= koren:
                if st / i == st // i:#vsota je deljiva s številom
                    if tabela[i] + tabela[int(st/i)] < tabela[st]:
                        tabela[st] = tabela[int(st/i)] + tabela[i]
                        tabela_zapis[st] = (int(st/i),'*',i)
                        
    return izpisi(tabela_zapis)
            
def izpisi(tabela):
    if tabela[-1] == 1:
        return '1'
    niz = ''
    prvo,operacija,drugo = tabela[-1]
    prvi_del = izpisi(tabela[:prvo+1])
    drugi_del = izpisi(tabela[:drugo+1])
    if prvi_del == '1' and drugi_del == '1':
        return  prvi_del  + operacija +  drugi_del
    
    if prvi_del == '1':
        
        return  prvi_del  + operacija + '(' + drugi_del +')'
    if drugi_del == '1':
        return  '(' + prvi_del +')' + operacija + drugi_del 
        
    return '(' + prvi_del +')' + operacija + '(' + drugi_del +')'