import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long N = sc.nextLong(); solve(N); } static void solve(long N){ ArrayList prime = prime(N); int [] num = decomposition(N,prime); long ans=1; for(int i=0; i prime(long N){ int UP = (int)Math.sqrt(N)+1; boolean [] b = new boolean [UP+1]; ArrayList prime = new ArrayList<>(); prime.add(2); for(int i=3; i<=UP; i+=2){ if(b[i]==false){ prime.add(i); int X=3*i; int Y=2*i; while(X<=UP){ b[X]=true; X+=Y; } } } //for(int i=0; i prime){ int [] num = new int [prime.size()+1]; for(int i=0; i