NrDiv

#include <iostream>
using namespace std;
int t[]={0, 3,5,7,11,13,17,19,23};
int c[]={0,15,7,6, 4, 2, 2, 2, 2};
int n,st[12],nrdiv;
long long numarimpar;
int d[12];

void nrdivizori()/// Calculez numarul de divizori ai lui x
{
    int i;
    for(i=1;i*i<n;++i)
        if(n%i==0)
            nrdiv+=2;
    if(i*i==n)
        ++nrdiv;
}

inline bool valid(int top)
{
    d[top]=d[top-1]*(1+st[top]);
    if(d[top]<=nrdiv)
        return true;
    return false;
}

inline int putere(int a,int k) /// Calculez p=a^k
{
    int p=1;
    for(int i=1;i<=k;++i)
        p*=a;
    return p;
}

inline void actualizaresolutie(int top)
{
    long long p=1;
    for(int i=1;i<=top;++i)
        p*=putere(t[i],st[i]);
    numarimpar=min(numarimpar,p);
}

inline void backtracking()
{
    bool gata;
    int top;
    d[0]=1;
    top=1;
    st[top]=0;
    while(top>0)
    {
        gata=false;
        while(!gata&&st[top]<c[top])
            ++st[top],gata=valid(top);
        if(!gata)
            --top;
        else
            if(d[top]==nrdiv)
                actualizaresolutie(top);
            else
                if(top<8)
                    st[++top]=0;
    }
}

int main()
{
    numarimpar=2000000000;
    cin>>n;
    nrdivizori();
    backtracking();
    cout<<numarimpar<<'\n';
    return 0;
}