#include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; using namespace std; #define mod 1000003 #define INF 10000000 #define LLINF 2000000000000000000LL #define SIZE 100000 vector factor(ll n){ vector ret,ret2; for(ll i=1;i*i<=n;i++){ if(n%i==0){ ret.push_back(i); if(i*i fac; cin >> n; fac = factor(n); for(int i=1;i