/*
nを素因数分解した結果を返す
ex)
720=(2^4)*(3^2)*(5^1)
[(2,4),(3,2),(5,1)]
*/
template <typename T>
vector<pair<T, T>> prime_factor(T n)
{
    vector<pair<T, T>> ret;
    T now = n;
    for (T i = 2; i * i <= n; i++)
    {
        T count = 0;
        while (now % i == 0)
        {
            now /= i;
            count++;
        }
        if (count != 0)
            ret.push_back(make_pair(i, count));
    }
    if (now != 1)
        ret.push_back(make_pair(now, 1));
    return ret;
}