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.
#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct Z_p {
  using Type = typename decay<decltype(T::value)>::type;
  static vector<Type> mod_inv;
  constexpr Z_p() : value() {}
  template <typename U>
  Z_p(const U &x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U &x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
  const Type &operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Z_p &operator+=(const Z_p &otr) {
    if ((value += otr.value) >= mod()) value -= mod();
    return *this;
  }
  Z_p &operator-=(const Z_p &otr) {
    if ((value -= otr.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Z_p &operator+=(const U &otr) {
    return *this += Z_p(otr);
  }
  template <typename U>
  Z_p &operator-=(const U &otr) {
    return *this -= Z_p(otr);
  }
  Z_p &operator++() { return *this += 1; }
  Z_p &operator--() { return *this -= 1; }
  Z_p operator++(int) {
    Z_p result(*this);
    *this += 1;
    return result;
  }
  Z_p operator--(int) {
    Z_p result(*this);
    *this -= 1;
    return result;
  }
  Z_p operator-() const { return Z_p(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Z_p<U>::Type, int>::value, Z_p>::type &
  operator*=(const Z_p &rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Z_p<U>::Type, int64_t>::value, Z_p>::type
      &
      operator*=(const Z_p &rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) *
                                     rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Z_p<U>::Type>::value, Z_p>::type &
  operator*=(const Z_p &rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  Z_p operator^(long long e) const {
    Z_p b = *this, res = 1;
    if (e < 0) b = 1 / b, e = -e;
    for (; e; b *= b, e >>= 1)
      if (e & 1) res *= b;
    return res;
  }
  Z_p &operator^=(const long long &e) { return *this = *this ^ e; }
  Z_p &operator/=(const Z_p &otr) {
    Type a = otr.value, m = mod(), u = 0, v = 1;
    if (a < int(mod_inv.size())) return *this *= mod_inv[a];
    while (a) {
      Type t = m / a;
      m -= t * a;
      swap(a, m);
      u -= t * v;
      swap(u, v);
    }
    assert(m == 1);
    return *this *= u;
  }
  template <typename U>
  friend const Z_p<U> &abs(const Z_p<U> &v) {
    return v;
  }
  Type value;
};
template <typename T>
bool operator==(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
bool operator==(const Z_p<T> &lhs, U rhs) {
  return lhs == Z_p<T>(rhs);
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
bool operator==(U lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
bool operator!=(const Z_p<T> &lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
bool operator!=(U lhs, const Z_p<T> &rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
bool operator>(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return lhs.value > rhs.value;
}
template <typename T>
bool operator<=(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return lhs.value <= rhs.value;
}
template <typename T>
bool operator>=(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return lhs.value >= rhs.value;
}
template <typename T>
Z_p<T> operator+(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) += rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator+(const Z_p<T> &lhs, U rhs) {
  return Z_p<T>(lhs) += rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator+(U lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) += rhs;
}
template <typename T>
Z_p<T> operator-(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) -= rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator-(const Z_p<T> &lhs, U rhs) {
  return Z_p<T>(lhs) -= rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator-(U lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) -= rhs;
}
template <typename T>
Z_p<T> operator*(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) *= rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator*(const Z_p<T> &lhs, U rhs) {
  return Z_p<T>(lhs) *= rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator*(U lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) *= rhs;
}
template <typename T>
Z_p<T> operator/(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) /= rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator/(const Z_p<T> &lhs, U rhs) {
  return Z_p<T>(lhs) /= rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator/(U lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) /= rhs;
}
template <typename T>
istream &operator>>(istream &in, Z_p<T> &number) {
  typename common_type<typename Z_p<T>::Type, int64_t>::type x;
  in >> x;
  number.value = Z_p<T>::normalize(x);
  return in;
}
template <typename T>
ostream &operator<<(ostream &out, const Z_p<T> &number) {
  return out << number();
}
constexpr int mod = (119 << 23) + 1;
using Zp = Z_p<integral_constant<decay<decltype(mod)>::type, mod>>;
template <typename T>
vector<typename Z_p<T>::Type> Z_p<T>::mod_inv;
template <typename T = integral_constant<decay<decltype(mod)>::type, mod>>
void precalc_inverse(size_t SZ) {
  auto &inv = Z_p<T>::mod_inv;
  if (inv.empty()) inv.assign(2, 1);
  for (; inv.size() <= SZ;)
    inv.push_back(
        (mod - 1LL * mod / int(inv.size()) * inv[mod % int(inv.size())] % mod) %
        mod);
}
template <int SZ>
struct number_theory {
  vector<int> lpf, prime, mu, phi;
  number_theory() : lpf(SZ + 1), mu(SZ + 1, 1), phi(SZ + 1, 1) {
    for (int i = 2; i <= SZ; ++i) {
      if (!lpf[i]) lpf[i] = i, prime.push_back(i);
      if (i / lpf[i] % lpf[i])
        mu[i] = -mu[i / lpf[i]], phi[i] = phi[i / lpf[i]] * (lpf[i] - 1);
      else
        mu[i] = 0, phi[i] = phi[i / lpf[i]] * lpf[i];
      for (int j = 0;
           j < int(prime.size()) && prime[j] <= lpf[i] && prime[j] * i <= SZ;
           ++j)
        lpf[prime[j] * i] = prime[j];
    }
  }
};
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(ios::badbit | ios::failbit);
  int m;
  cin >> m;
  const int mx = 1e5;
  number_theory<mx> nt;
  vector<int> freq(mx + 1);
  for (auto rep = 0; rep < m; ++rep) {
    int x, f;
    cin >> x >> f;
    freq[x] = f;
  }
  Zp res = 0;
  for (auto x = 1; x <= mx; ++x) {
    Zp sum = 0, sqsum = 0, cur = 0;
    long long n = 0;
    for (auto y = x; y <= mx; y += x) {
      sum += Zp(freq[y]) * y;
      sqsum += Zp(freq[y]) * y * y;
      n += freq[y];
    }
    if (n >= 2) {
      cur = ((n - 1) * sqsum + n * (sum * sum - sqsum) / 2) * (Zp(2) ^ n - 2);
      res += nt.mu[x] * cur;
      42;
    }
  }
  cout << res << "\n";
  return 0;
}
