#include <utility>
#include <vector>
#include <cmath>

std::vector<std::pair<int64_t, int>> Factorize(int64_t x) {
    std::vector<std::pair<int64_t, int>> result;
    for (int64_t divider = 2; divider < std::sqrt(x) + 1; ++divider) {
        if (x % divider == 0) {
            int counter = 0;
            while (x % divider == 0) {
                ++counter;
                x /= divider;
            }
            result.emplace_back(divider, counter);
        }
    }
    if (x > 1) {
        result.emplace_back(x, 1);
    }
    return result;
}