/*
    author:  Maksim1744
    created: 27.01.2024 11:49:52
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

struct Sieve {
    struct PrimeIterator {
        int prime;
        int count;
        int num;
        const Sieve& sieve;

        PrimeIterator(int num, const Sieve& sieve) : num(num), sieve(sieve) {
            step();
        }

        void step() {
            prime = sieve.mn[num];
            count = 0;
            while (num != 1 && sieve.mn[num] == prime) {
                num /= sieve.mn[num];
                ++count;
            }
        }

        bool operator == (const PrimeIterator& other) const {
            return tie(prime, count, num) == tie(other.prime, other.count, other.num);
        }
        bool operator != (const PrimeIterator& other) const {
            return !(*this == other);
        }

        PrimeIterator& operator ++ () {
            step();
            return *this;
        }

        pair<int, int> operator * () const {
            return {prime, count};
        }
    };

    struct PrimeIteratorContainer {
        int num;
        const Sieve& sieve;
        using iterator = PrimeIterator;

        PrimeIteratorContainer(int num, const Sieve& sieve) : num(num), sieve(sieve) {}

        PrimeIterator begin() const {
            return PrimeIterator(num, sieve);
        }

        PrimeIterator end() const {
            return PrimeIterator(1, sieve);
        }

        vector<pair<int, int>> collect() const {
            vector<pair<int, int>> result;
            for (auto p : *this)
                result.push_back(p);
            return result;
        }
    };

    template<typename U, typename V>
    struct DoubleIterator {
        U u;
        V v;
        U::iterator uit;
        V::iterator vit;
        int prime;
        int count;

        DoubleIterator(const U& u, const V& v, U::iterator uit, V::iterator vit) : u(u), v(v), uit(uit), vit(vit) {
            tie(prime, count) = this->operator*();
        }

        DoubleIterator& operator ++ () {
            if (uit == u.end()) {
                ++vit;
            } else if (vit == v.end()) {
                ++uit;
            } else if ((*uit).first < (*vit).first) {
                ++uit;
            } else if ((*uit).first > (*vit).first) {
                ++vit;
            } else {
                ++uit;
                ++vit;
            }
            return *this;
        }

        bool operator == (const DoubleIterator& other) const {
            return tie(uit, vit) == tie(other.uit, other.vit);
        }
        bool operator != (const DoubleIterator& other) const {
            return !(*this == other);
        }

        pair<int, int> operator * () const {
            if (uit == u.end()) return *vit;
            if (vit == v.end()) return *uit;
            if ((*uit).first < (*vit).first) return *uit;
            if ((*uit).first > (*vit).first) return *vit;
            return {(*uit).first, (*uit).second + (*vit).second};
        }
    };

    template<typename U, typename V>
    struct DoubleIteratorContainer {
        using iterator = DoubleIterator<U, V>;
        U u;
        V v;

        DoubleIteratorContainer(const U& u, const V& v) : u(u), v(v) {}

        iterator begin() const {
            return iterator(u, v, u.begin(), v.begin());
        }

        iterator end() const {
            return iterator(u, v, u.end(), v.end());
        }

        vector<pair<int, int>> collect() const {
            vector<pair<int, int>> result;
            for (auto p : *this)
                result.push_back(p);
            return result;
        }
    };

    vector<bool> isp;
    vector<int> primes;
    vector<int> mn;

    Sieve(int n, bool gen_primes = false, bool gen_mn = false) {
        isp.assign(n + 1, true); isp[0] = isp[1] = false;
        for (int i = 2; i * i <= n; ++i)
            if (isp[i])
                for (int j = i * i; j <= n; j += i)
                    isp[j] = false;

        if (gen_primes)
            for (int i = 2; i <= n; ++i)
                if (isp[i])
                    primes.push_back(i);

        if (gen_mn) {
            mn.assign(n + 1, -1);
            for (int i = 2; i <= n; ++i) {
                if (isp[i]) {
                    mn[i] = i;
                    if ((ll)i * i <= n)
                        for (int j = i * i; j <= n; j += i)
                            if (mn[j] == -1)
                                mn[j] = i;
                }
            }
        }
    }

    bool is_prime(int k) const {
        return isp[k];
    }

    bool operator[](int k) const {
        return isp[k];
    }

    // can be used as vector<pair<int, int>>, as in function phi() below
    // except doesn't create a vector to avoid heap allocations
    // can be transformed into vector<pair<int, int>> with .collect()
    auto get_prime_divs(int p) const {
        return PrimeIteratorContainer(p, *this);
    }

    // if you want to get prime divs for n = a * b * c where max(a, b, c) < size(sieve), then call get_prime_divs(a, b, c)
    template<typename... Args>
    auto get_prime_divs(int p, Args... args) const {
        return DoubleIteratorContainer(PrimeIteratorContainer(p, *this), get_prime_divs(args...));
    }

    int phi(int n) const {
        auto v = get_prime_divs(n);
        for (auto [p, c] : v)
            n = n / p * (p - 1);
        return n;
    }
};

namespace mint_ns {
template<auto P>
struct Modular {
    using value_type = decltype(P);
    value_type value;

    Modular(long long k = 0) : value(norm(k)) {}

    friend Modular<P>& operator += (      Modular<P>& n, const Modular<P>& m) { n.value += m.value; if (n.value >= P) n.value -= P; return n; }
    friend Modular<P>  operator +  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r += m; }

    friend Modular<P>& operator -= (      Modular<P>& n, const Modular<P>& m) { n.value -= m.value; if (n.value < 0)  n.value += P; return n; }
    friend Modular<P>  operator -  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r -= m; }
    friend Modular<P>  operator -  (const Modular<P>& n)                      { return Modular<P>(-n.value); }

    friend Modular<P>& operator *= (      Modular<P>& n, const Modular<P>& m) { n.value = n.value * 1ll * m.value % P; return n; }
    friend Modular<P>  operator *  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r *= m; }

    friend Modular<P>& operator /= (      Modular<P>& n, const Modular<P>& m) { return n *= m.inv(); }
    friend Modular<P>  operator /  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r /= m; }

    Modular<P>& operator ++ (   ) { return *this += 1; }
    Modular<P>& operator -- (   ) { return *this -= 1; }
    Modular<P>  operator ++ (int) { Modular<P> r = *this; *this += 1; return r; }
    Modular<P>  operator -- (int) { Modular<P> r = *this; *this -= 1; return r; }

    friend bool operator == (const Modular<P>& n, const Modular<P>& m) { return n.value == m.value; }
    friend bool operator != (const Modular<P>& n, const Modular<P>& m) { return n.value != m.value; }

    explicit    operator       int() const { return value; }
    explicit    operator      bool() const { return value; }
    explicit    operator long long() const { return value; }

    constexpr static value_type mod()      { return     P; }

    value_type norm(long long k) {
        if (!(-P <= k && k < P)) k %= P;
        if (k < 0) k += P;
        return k;
    }

    Modular<P> inv() const {
        value_type a = value, b = P, x = 0, y = 1;
        while (a != 0) { value_type k = b / a; b -= k * a; x -= k * y; swap(a, b); swap(x, y); }
        return Modular<P>(x);
    }
};
template<auto P> Modular<P> pow(Modular<P> m, long long p) {
    Modular<P> r(1);
    while (p) {
        if (p & 1) r *= m;
        m *= m;
        p >>= 1;
    }
    return r;
}

template<auto P> ostream& operator << (ostream& o, const Modular<P>& m) { return o << m.value; }
template<auto P> istream& operator >> (istream& i,       Modular<P>& m) { long long k; i >> k; m.value = m.norm(k); return i; }
template<auto P> string   to_string(const Modular<P>& m) { return to_string(m.value); }

// using Mint = long double;
}
using namespace mint_ns;

using Mint1 = Modular<1000000007>;
using Mint2 = Modular<998244353>;

const Mint1 P1 = 1238796;
const Mint2 P2 = 9123606;

vector<Mint1> degp1;
vector<Mint2> degp2;

namespace segtree {

// This implementation is disgusting, but it seems to work and do it faster than previous version.

template<typename Item>
Item tree_merge(const Item& a, const Item& b) {
    Item i;
    i.update(a, b);
    return i;
}

template<typename Item, bool lazy>
struct Pusher {};

template<typename Item>
struct Pusher<Item, false> {
    void push(const vector<Item>&, int, int, int) {}
    Item ask_on_segment(const vector<Item>& tree, int n, int l, int r) {
        l |= n;
        r |= n;
        Item resl, resr;
        while (l <= r) {
            if (l & 1) {
                resl = tree_merge(resl, tree[l]);
                ++l;
            }
            if (!(r & 1)) {
                resr = tree_merge(tree[r], resr);
                --r;
            }
            l >>= 1;
            r >>= 1;
        }
        return tree_merge(resl, resr);
    }
    void push_point(const vector<Item>&, int, int) {}

    template<typename P>
    int lower_bound(const vector<Item>& tree, int n, int l, P p) {
        Item cur;
        if (p(cur)) return l - 1;
        l |= n;
        int r = n | (n - 1);
        // carefully go up
        while (true) {
            if (p(tree_merge(cur, tree[l]))) {
                break;
            }
            if (l == r) return n;
            if (l & 1) {
                cur = tree_merge(cur, tree[l]);
                ++l;
            }
            l >>= 1;
            r >>= 1;
        }

        // usual descent from l
        while (l < n) {
            if (p(tree_merge(cur, tree[l * 2]))) {
                l = l * 2;
            } else {
                cur = tree_merge(cur, tree[l * 2]);
                l = l * 2 + 1;
            }
        }
        return (l ^ n);
    }

    template<typename P>
    int lower_bound_rev(const vector<Item>& tree, int n, int r, P p) {
        Item cur;
        if (p(cur)) return r + 1;
        r |= n;
        int l = n;
        // carefully go up
        while (true) {
            if (p(tree_merge(tree[r], cur))) {
                break;
            }
            if (l == r) return -1;
            if (!(r & 1)) {
                cur = tree_merge(tree[r], cur);
                --r;
            }
            l >>= 1;
            r >>= 1;
        }

        // usual descent from r
        while (r < n) {
            if (p(tree_merge(tree[r * 2 + 1], cur))) {
                r = r * 2 + 1;
            } else {
                cur = tree_merge(tree[r * 2 + 1], cur);
                r = r * 2;
            }
        }
        return (r ^ n);
    }
};

template<typename Item>
struct Pusher<Item, true> {
    void push(vector<Item>& tree, int ind, int l, int r) {
        tree[ind].push(tree[ind * 2], tree[ind * 2 + 1], l, r);
    }

    Item ask_on_segment(vector<Item>& tree, int n, int l, int r) {
        int vl = 0, vr = n - 1;
        int i = 1;
        Item result;
        while (vl != vr) {
            int m = (vl + vr) / 2;
            if (l > m) {
                push(tree, i, vl, vr);
                i = i * 2 + 1;
                vl = m + 1;
            } else if (r <= m) {
                push(tree, i, vl, vr);
                i = i * 2;
                vr = m;
            } else {
                break;
            }
        }
        if (l == vl && r == vr) {
            return tree[i];
        }
        push(tree, i, vl, vr);
        // left
        {
            int ind = i * 2;
            int L = vl, R = (vl + vr) / 2;
            while (l != L) {
                int m = (L + R) / 2;
                push(tree, ind, L, R);
                if (l <= m) {
                    result = tree_merge(tree[ind * 2 + 1], result);
                    ind *= 2;
                    R = m;
                } else {
                    ind = ind * 2 + 1;
                    L = m + 1;
                }
            }
            result = tree_merge(tree[ind], result);
        }
        // right
        {
            int ind = i * 2 + 1;
            int L = (vl + vr) / 2 + 1, R = vr;
            while (r != R) {
                int m = (L + R) / 2;
                push(tree, ind, L, R);
                if (r > m) {
                    result = tree_merge(result, tree[ind * 2]);
                    ind = ind * 2 + 1;
                    L = m + 1;
                } else {
                    ind = ind * 2;
                    R = m;
                }
            }
            result = tree_merge(result, tree[ind]);
        }
        return result;
    }

    void push_point(vector<Item>& tree, int n, int ind) {
        int l = 0, r = n - 1;
        int i = 1;
        while (l != r) {
            push(tree, i, l, r);
            int m = (l + r) / 2;
            if (ind <= m) {
                r = m;
                i *= 2;
            } else {
                l = m + 1;
                i = i * 2 + 1;
            }
        }
    }

    template<typename P>
    pair<int, Item> _lower_bound(vector<Item>& tree, int l, P p, Item cur, int i, int vl, int vr) {
        if (vl == vr) {
            if (p(tree_merge(cur, tree[i]))) {
                return {vl, tree[i]};
            } else {
                return {vl + 1, tree[i]};
            }
        }

        push(tree, i, vl, vr);
        int m = (vl + vr) / 2;
        if (l > m) {
            return _lower_bound(tree, l, p, cur, i * 2 + 1, m + 1, vr);
        } else if (l <= vl) {
            if (!p(tree_merge(cur, tree[i]))) {
                return {vr + 1, tree_merge(cur, tree[i])};
            }
            if (p(tree_merge(cur, tree[i * 2]))) {
                return _lower_bound(tree, l, p, cur, i * 2, vl, m);
            } else {
                return _lower_bound(tree, l, p, tree_merge(cur, tree[i * 2]), i * 2 + 1, m + 1, vr);
            }
        } else {
            auto [ind, it] = _lower_bound(tree, l, p, cur, i * 2, vl, m);
            if (ind <= m) return {ind, it};
            return _lower_bound(tree, l, p, it, i * 2 + 1, m + 1, vr);
        }
    }

    template<typename P>
    int lower_bound(vector<Item>& tree, int n, int l, P p) {
        Item cur;
        if (p(cur)) return l - 1;
        return _lower_bound(tree, l, p, cur, 1, 0, n - 1).first;
    }

    template<typename P>
    pair<int, Item> _lower_bound_rev(vector<Item>& tree, int r, P p, Item cur, int i, int vl, int vr) {
        if (vl == vr) {
            if (p(tree_merge(tree[i], cur))) {
                return {vl, tree[i]};
            } else {
                return {vl - 1, tree[i]};
            }
        }

        push(tree, i, vl, vr);
        int m = (vl + vr) / 2;
        if (r <= m) {
            return _lower_bound_rev(tree, r, p, cur, i * 2, vl, m);
        } else if (r >= vr) {
            if (!p(tree_merge(tree[i], cur))) {
                return {vl - 1, tree_merge(cur, tree[i])};
            }
            if (p(tree_merge(tree[i * 2 + 1], cur))) {
                return _lower_bound_rev(tree, r, p, cur, i * 2 + 1, m + 1, vr);
            } else {
                return _lower_bound_rev(tree, r, p, tree_merge(tree[i * 2 + 1], cur), i * 2, vl, m);
            }
        } else {
            auto [ind, it] = _lower_bound_rev(tree, r, p, cur, i * 2 + 1, m + 1, vr);
            if (ind > m) return {ind, it};
            return _lower_bound_rev(tree, r, p, it, i * 2, vl, m);
        }
    }

    template<typename P>
    int lower_bound_rev(vector<Item>& tree, int n, int r, P p) {
        Item cur;
        if (p(cur)) return r + 1;
        return _lower_bound_rev(tree, r, p, cur, 1, 0, n - 1).first;
    }
};

template<typename Item, bool lazy = false>
struct Segtree {
    vector<Item> tree;
    Pusher<Item, lazy> pusher;
    int n;
    int n0;

    Segtree(int n = 0) {
        build(n);
    }

    template<typename U>
    Segtree(const vector<U>& v) {
        build(v);
    }

    void build(int n) {
        this->n0 = n;
        while (n & (n - 1)) ++n;
        this->n = n;
        tree.assign(n * 2, {});
    }

    template<typename U>
    void build(const vector<U>& v) {
        build(v.size());
        for (int i = 0; i < v.size(); ++i) {
            tree[n | i].init(v[i], i);
        }
        build();
    }

    void build() {
        for (int i = n - 1; i >= 1; --i) {
            tree[i].update(tree[i * 2], tree[i * 2 + 1]);
        }
    }

    void push(int ind, int l, int r) {
        pusher.push(tree, ind, l, r);
    }

    template<typename T>
    void set(int ind, const T& t) {
        pusher.push_point(tree, n, ind);
        ind |= n;
        tree[ind].init(t, ind ^ n);
        ind >>= 1;
        while (ind) {
            tree[ind].update(tree[ind * 2], tree[ind * 2 + 1]);
            ind >>= 1;
        }
    }

    template<typename T>
    void update(int ind, const T& t) {
        pusher.push_point(tree, n, ind);
        ind |= n;
        tree[ind].update(t, ind ^ n);
        ind >>= 1;
        while (ind) {
            tree[ind].update(tree[ind * 2], tree[ind * 2 + 1]);
            ind >>= 1;
        }
    }

    Item& ith(int ind) {
        static_assert(!lazy, "don't use this method with lazy propagation, unless you're sure you need it");
        return tree[ind | n];
    }

    const Item& root() const {
        return tree[1];
    }

    Item ask(int l, int r) {
        l = max(l, 0);
        r = min(r, n - 1);
        if (l > r) return {};
        return pusher.ask_on_segment(tree, n, l, r);
    }

    template<typename T>
    void modify(int l, int r, const T& t) {
        static_assert(lazy, "lazy must be set to true to use this function");
        l = max(l, 0);
        r = min(r, n - 1);
        if (l > r) return;
        int vl = 0, vr = n - 1;
        int i = 1;
        while (vl != vr) {
            int m = (vl + vr) / 2;
            if (l > m) {
                push(i, vl, vr);
                i = i * 2 + 1;
                vl = m + 1;
            } else if (r <= m) {
                push(i, vl, vr);
                i = i * 2;
                vr = m;
            } else {
                break;
            }
        }
        if (l == vl && r == vr) {
            tree[i].modify(t, l, r);
        } else {
            push(i, vl, vr);
            // left
            {
                int ind = i * 2;
                int L = vl, R = (vl + vr) / 2;
                while (l != L) {
                    int m = (L + R) / 2;
                    push(ind, L, R);
                    if (l <= m) {
                        tree[ind * 2 + 1].modify(t, m + 1, R);
                        ind *= 2;
                        R = m;
                    } else {
                        ind = ind * 2 + 1;
                        L = m + 1;
                    }
                }
                tree[ind].modify(t, L, R);
                ind >>= 1;
                while (ind != i) {
                    tree[ind].update(tree[ind * 2], tree[ind * 2 + 1]);
                    ind >>= 1;
                }
            }
            // right
            {
                int ind = i * 2 + 1;
                int L = (vl + vr) / 2 + 1, R = vr;
                while (r != R) {
                    int m = (L + R) / 2;
                    push(ind, L, R);
                    if (r > m) {
                        tree[ind * 2].modify(t, L, m);
                        ind = ind * 2 + 1;
                        L = m + 1;
                    } else {
                        ind = ind * 2;
                        R = m;
                    }
                }
                tree[ind].modify(t, L, R);
                ind >>= 1;
                while (ind != i) {
                    tree[ind].update(tree[ind * 2], tree[ind * 2 + 1]);
                    ind >>= 1;
                }
            }
            tree[i].update(tree[i * 2], tree[i * 2 + 1]);
        }
        i >>= 1;
        while (i) {
            tree[i].update(tree[i * 2], tree[i * 2 + 1]);
            i >>= 1;
        }
    }

    // first index r such that p(tree.ask(l, r)) == true
    // if p() is true for empty item, return l-1
    // if p() is never true, returns n
    template<typename P>
    int lower_bound(int l, P p) {
        l = max(l, 0);
        if (l >= n0) return n0;
        return min(n0, pusher.lower_bound(tree, n, l, p));
    }

    // similarly to lower_bound, returns first (largest) l such that p(tree.ask(l, r)) == true
    template<typename P>
    int lower_bound_rev(int r, P p) {
        r = min(r, n0 - 1);
        if (r < 0) return -1;
        return pusher.lower_bound_rev(tree, n, r, p);
    }
};

}
using segtree::Segtree;

struct Item {
    Mint1 h1 = 0;
    Mint2 h2 = 0;
    int len = 0;

    template<typename T>
    void init(const T& t, int ind) {
        h1 = t;
        h2 = t;
        len = 1;
    }

    void update(const Item& a, const Item& b) {
        h1 = a.h1 + b.h1 * degp1[a.len];
        h2 = a.h2 + b.h2 * degp2[a.len];
        len = a.len + b.len;
    }

    // similar to init, but more convenient for doing a[i] += x, implement only if needed
    template<typename T>
    void update(const T& t, int ind) {
        h1 += t;
        h2 += t;
    }

    //// apply here, save for children
    // template<typename T>
    // void modify(const T& m, int l, int r) {}

    // void push(Item& a, Item& b, int l, int r) {
    //     int m = (l + r) / 2;
    //     a.modify(mod, l, m);
    //     b.modify(mod, m + 1, r);
    //     // reset mod
    // }
};

// finds x and y such that a * x + b * y = c
template<typename T>
pair<T, T> egcd(T a, T b, T c) {
    if (a == 0) {
        // b * y = c
        assert(c % b == 0);
        return {0, c / b};
    }
    // a * x + b * y = c
    // a * x + (b % a + (b/a) * a) * y = c
    // a * (x + (b/a) * y) + (b % a) * y = c
    auto [y0, x0] = egcd(b % a, a, c);
    T y = y0;
    T x = x0 - (b / a) * y;
    return {x, y};
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    degp1.pb(1);
    degp2.pb(1);

    int n;
    cin >> n;
    vector<pair<int, int>> v(n);
    cin >> v;

    const int N = 1e5 + 20;

    Sieve sieve(N, true, true);
    for (auto& [p, q] : v) {
        int g = gcd(p, q);
        p /= g;
        q /= g;
    }

    vector<int> maxd(N, 0);

    for (int i = 0; i < n; ++i) {
        for (auto [p, c] : sieve.get_prime_divs(v[i].second)) {
            maxd[p] = max(maxd[p], c);
        }
    }

    vector<int> ind(N);
    int last = 0;

    for (int i = 0; i < N; ++i) {
        if (maxd[i] > 0) {
            ind[i] = last;
            ++last;
        }
    }
    if (!last) ++last;

    vector<int> cur(last, 0);

    for (int i = 0; i < cur.size() + 10; ++i) {
        degp1.pb(degp1.back() * P1);
        degp2.pb(degp2.back() * P2);
    }

    Segtree<Item, false> tree(cur);

    map<pair<int, int>, ll> cnts;
    auto mem = [&]() {
        cnts[{(int)tree.root().h1, (int)tree.root().h2}]++;
    };

    mem();

    auto mpow = [&](ll a, ll p) {
        ll r = 1;
        while (p) {
            if (p & 1) r *= a;
            a *= a;
            p >>= 1;
        }
        return r;
    };

    auto inv = [&](ll a, ll mod) {
        a %= mod;
        // a * x = 1 + mod * y
        auto [x, y] = egcd<ll>(a, -mod, 1);
        x = (x % mod + mod) % mod;
        assert(x * a % mod == 1);
        return x;
    };

    for (int i = 0; i < n; ++i) {
        shows;
        show(i);
        auto [p, q] = v[i];
        for (auto [p1, c1] : sieve.get_prime_divs(q)) {
            ll who = mpow(p1, maxd[p1]);
            ll p0 = p * mpow(p1, maxd[p1] - c1) % who;
            ll q0 = q / mpow(p1, c1);

            int val = p0 * inv(q0, who);
            cur[ind[p1]] = (cur[ind[p1]] + val) % who;
            tree.set(ind[p1], cur[ind[p1]]);
        }

        mem();
    }

    ll ans = 0;
    for (const auto& [p, c] : cnts)
        ans += c * (c - 1) / 2;
    cout << ans << '\n';

    return 0;
}