#include <bits/stdc++.h>
std::map<unsigned long long, unsigned> prime_factorize(unsigned long long x) {
	std::map<unsigned long long, unsigned> ret;
	for (unsigned i = 2; 1ULL * i * i <= x; i++) {
		while (x % i == 0) x /= i, ret[i]++;
	}
	if (x != 1) ret[x]++;
	return ret;
}