static void PrimeFactorization(int n) {//O(sqrt(N))
    List<Integer> p = new ArrayList<>();
    for (int i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            p.add(i);
            n /= i;
        }
    }
    if (n != 1) {
        p.add(n);
    }
}