Given the number *n*, find the smallest positive integer which has exactly *n* divisors. It is guaranteed that for the given *n* the answer will not exceed 10<sup class="upper-index">18</sup>.
The first line of the input contains integer *n* (1 ≤ *n* ≤ 1000).
#include<bits/stdc++.h>
#define int  long long
#define mod  1000000007
#define test freopen("1.txt","r",stdin);
#define endl "\n"
#define ff first
#define ss second
using namespace std;
int MAXV=2e18;
vector<int>primes={2,3,5,7,11,13,17,19,23,29,31,37,41};
int f(int num,int factors,int i,int n){
if(factors==n){
    return num;
}
if(i==primes.size())return MAXV;
if(n<0)return MAXV;
if(num>MAXV)return MAXV;
int ret=MAXV;
for(int power=0;power<=63;power++){
    if(factors*(power+1)>n or num>MAXV)break;
    ret=min(ret,f(num*pow(primes[i],power),factors*(power+1),i+1,n));
}
return ret;
}
signed main(){
int n;cin>>n;
cout<<f(1,1,0,n);
return 0;
}