vector<pair<int,int>> fact(int n) {
    vector<pair<int,int>> result;
    for (int p = 2; p*p <= n; ++p) {
        if (n % p == 0) {
            result.emplace_back(p, 0);
            while (n % p == 0) {
                ++result.back().second;
                n /= p;
            }
        }
    }
    if (n > 1) {
        result.push_back(n, 1);
    }
    return result;
}