Problem: You are given a multiset S. Over all pairs of subsets A and B, such that:

  * B ⊂ A; 
  * |B| = |A| - 1; 
  * greatest common divisor of all elements in A is equal to one; 



find the sum of ∑_{x ∈ A}{x} ⋅ ∑_{x ∈ B}{x}, modulo 998 244 353.

Input

The first line contains one integer m (1 ≤ m ≤ 10^5): the number of different values in the multiset S.

Each of the next m lines contains two integers a_i, freq_i (1 ≤ a_i ≤ 10^5, 1 ≤ freq_i ≤ 10^9). Element a_i appears in the multiset S freq_i times. All a_i are different.

Output

Print the required sum, modulo 998 244 353.

Examples

Input


2
1 1
2 1


Output


9


Input


4
1 1
2 1
3 1
6 1


Output


1207


Input


1
1 5


Output


560

Note

A multiset is a set where elements are allowed to coincide. |X| is the cardinality of a set X, the number of elements in it.

A ⊂ B: Set A is a subset of a set B.

In the first example B=\{1\}, A=\{1,2\} and B=\{2\}, A=\{1, 2\} have a product equal to 1⋅3 + 2⋅3=9. Other pairs of A and B don't satisfy the given constraints.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
template <int MOD>
struct Integral {
  int v_ = 0;
  template <typename T>
  Integral(T v) : v_(norm(v)) {
    static_assert(std::is_integral<T>::value, "input should be an integral.");
  }
  Integral() = default;
  ~Integral() = default;
  template <typename T>
  T norm(T v) const {
    if constexpr (std::is_same<long long, T>::value) {
      v %= MOD;
      if (v < 0) v += MOD;
    } else {
      if (v >= MOD) v -= MOD;
      if (v < 0) v += MOD;
      if (v >= MOD || v < 0) {
        v %= MOD;
        if (v < 0) v += MOD;
      }
    }
    return v;
  }
  int val() const { return v_; }
  Integral operator+(const Integral& rhs) const {
    return Integral(val() + rhs.val());
  }
  Integral operator-(const Integral& rhs) const {
    return Integral(val() - rhs.val());
  }
  Integral operator*(const Integral& rhs) const {
    return Integral(val() * 1LL * rhs.val());
  }
  Integral operator/(const Integral& rhs) const { return *this * rhs.inv(); }
  Integral& operator+=(const Integral& rhs) { return *this = *this + rhs; }
  Integral& operator-=(const Integral& rhs) { return *this = *this - rhs; }
  Integral& operator*=(const Integral& rhs) { return *this = *this * rhs; }
  Integral& operator/=(const Integral& rhs) { return *this = *this / rhs; }
  bool operator==(const Integral& rhs) const { return val() == rhs.val(); }
  bool operator!=(const Integral& rhs) const { return !(*this == rhs); }
  const Integral operator-() const { return Integral(-val()); }
  const Integral operator++() {
    v_ = norm(v_ + 1);
    return *this;
  }
  const Integral operator++(int) {
    Integral ret = *this;
    ++(*this);
    return ret;
  }
  const Integral operator--() {
    v_ = norm(v_ - 1);
    return *this;
  }
  const Integral operator--(int) {
    Integral ret = *this;
    --(*this);
    return ret;
  }
  Integral power(long long b) const {
    long long ret = 1 % MOD, a = v_;
    for (; b; b >>= 1, a = a * a % MOD)
      if (b & 1) ret = ret * a % MOD;
    return ret;
  }
  Integral inv() const { return power(MOD - 2); }
};
template <int MOD>
std::string to_string(const Integral<MOD>& v) {
  return std::string("Int<>{") + std::to_string(v.val()) + "}";
}
template <int MOD, bool kAllowBruteForce = false>
struct Binomial {
  std::vector<Integral<MOD>> factor, inv_factor;
  explicit Binomial(int n = 0) : factor(n + 1), inv_factor(n + 1) {
    factor[0] = 1;
    for (int i = 1; i <= n; ++i) factor[i] = factor[i - 1] * i;
    inv_factor[n] = factor[n].inv();
    for (int i = n; i >= 1; --i) inv_factor[i - 1] = inv_factor[i] * i;
  }
  ~Binomial() = default;
  template <typename T>
  Integral<MOD> operator()(T a, T b) const {
    if (a < b || b < 0) return 0;
    if (a < factor.size()) return factor[a] * inv_factor[b] * inv_factor[a - b];
    if constexpr (!kAllowBruteForce) {
      throw std::out_of_range("Binomial");
    } else {
      b = std::min(b, a - b);
      Integral<MOD> ret = 1;
      for (T i = 1; i <= b; ++i) ret = ret * (a + 1 - i) / i;
      return ret;
    }
  }
};
template <int MOD>
struct PowerTable : public std::vector<Integral<MOD>> {
  PowerTable(int n, const Integral<MOD>& g) {
    static_assert(sizeof(PowerTable) == sizeof(std::vector<Integral<MOD>>), "");
    this->resize(n + 1);
    this->at(0) = 1;
    this->at(1) = g;
    for (int i = 2; i < this->size(); ++i)
      this->at(i) = this->at(i - 1) * this->at(1);
  }
};
const int MOD = 998244353;
using Mint = Integral<MOD>;
using Binom = Binomial<MOD>;
using LL = long long;
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;
  int m;
  reader >> m;
  int n = 100000;
  std::vector<Mint> sum(n + 1), sum2(n + 1), sump(n + 1);
  std::vector<LL> cnt(n + 1);
  for (int i = 0; i < m; ++i) {
    int a, f;
    reader >> a >> f;
    sum[a] += Mint(a) * f;
    sum2[a] += Mint(a) * a * f;
    sump[a] += Mint(a) * a * f * (f - 1);
    cnt[a] += f;
  }
  std::vector<Mint> f(n + 1);
  for (int i = n; i >= 1; --i) {
    Mint s, s2, sp;
    LL c = 0;
    for (int j = i; j <= n; j += i) {
      sp += sump[j] + s * sum[j] * 2;
      s += sum[j];
      s2 += sum2[j];
      c += cnt[j];
    }
    if (c >= 2) f[i] += s2 * (c - 1) * Mint(2).power(c - 2);
    if (c >= 3) f[i] += sp * Mint(c - 2) * Mint(2).power(c - 3);
    if (c >= 2) f[i] += sp * Mint(2).power(c - 2);
    for (int j = i + i; j <= n; j += i) {
      f[i] -= f[j];
    }
  }
  printf("%d\n", f[1].val());
}