#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; bool erasu[1000001]; vector prim; ll prime_factorization(ll n){ ll ans =1; /*for(int i=2; i*i<=n; i++)*/ for(int i=0; i>x; shieve(sqrt(x)); /* for(int i=0; i