#include #include "bits/stdc++.h" #include #include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; #define INF (1e9+1) #define rep(i,n) for(ll i=0;i<(ll)(n);i++) using namespace std; typedef pair P; ll prime_factorization(ll n){ ll ans =1; for(int i=2; i*i<=n; i++){ int cp=0; while(n%i ==0){ cp++; n /=i; } if(cp%2 !=0){ ans *= i; } } if( n !=1) ans *=n; return ans; } int main(){ ll x=0; cin>>x; cout<