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>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline long long rand(long long x, long long y) {
  return rng() % (y + 1 - x) + x;
}
string inline to_string(char c) {
  string second(1, c);
  return second;
}
template <typename T>
inline T gcd(T a, T b) {
  return a == 0 ? llabs(b) : gcd(b % a, a);
}
using ll = long long;
using ld = long double;
using pi = pair<ll, ll>;
using spi = pair<ll, pi>;
using dpi = pair<pi, pi>;
ll n, ans[(100006)], mod = 998244353, sum[4][(100006)];
pi A[(100006)];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (ll i = 1; i <= ll(n); ++i) cin >> A[i].first >> A[i].second;
  for (ll i = 1; i <= ll(n); ++i) {
    ll self = A[i].first * A[i].first % mod *
              (A[i].second * (A[i].second - 1) % mod) % mod;
    auto add = [&](ll x) {
      sum[2][x] +=
          (self + 2 * A[i].first * sum[0][x] % mod * A[i].second % mod),
          sum[2][x] %= mod;
      sum[1][x] += A[i].first * A[i].first % mod * A[i].second,
          sum[1][x] %= mod;
      sum[0][x] += A[i].first * A[i].second, sum[0][x] %= mod;
      sum[3][x] += A[i].second;
    };
    for (ll j = 1; j * j <= A[i].first; ++j)
      if (A[i].first % j == 0) {
        add(j);
        if (j * j ^ A[i].first) add(A[i].first / j);
      }
  }
  auto qexp = [&](ll x, ll e) {
    ll sum = 1;
    for (; e; e >>= 1, x *= x, x %= mod)
      if (e & 1) sum *= x, sum %= mod;
    return sum;
  };
  for (ll i = 1e5; i >= ll(1); --i) {
    ll t = sum[3][i];
    if (t > 1) ans[i] = (t - 1) % mod * qexp(2, t - 2) % mod * sum[1][i] % mod;
    if (t == 2)
      ans[i] += sum[2][i], ans[i] %= mod;
    else if (t > 2)
      ans[i] += t % mod * qexp(2, t - 3) % mod * sum[2][i], ans[i] %= mod;
    for (ll j = i * 2; j <= 1e5; j += i)
      ans[i] -= ans[j], ans[i] += mod, ans[i] %= mod;
  }
  cout << ans[1] << '\n';
}