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 ll = long long;
const int C = 100001, M = 998244353;
inline ll pow(ll a, ll b, ll M) {
  ll c = 1;
  while (b > 0) {
    if (b % 2 == 1) c = (c * a) % M;
    b /= 2;
    a = (a * a) % M;
  }
  return c;
}
int val[C];
ll aligned_pw[C], res[C];
int main() {
  int n, f, a, k;
  ll av2A_ = 0, av2 = 0, avA_ = 0, av = 0, count = 1, A_ = 0;
  ll s, sx0, sx1, sx2, sx3, s2, s3, inv6, pw, isq, i;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d %d", &a, &f), val[a] = f;
  inv6 = pow(6, M - 2, M);
  for (i = 0; i < C; i++) aligned_pw[i] = pow(2, M - 1 + val[i] - 3, M);
  for (k = C - 1; k > 0; k--) {
    av2A_ = 0, av2 = 0, avA_ = 0, av = 0, count = 1, A_ = 0;
    for (i = k; i < C; i += k) {
      s = val[i] % M;
      s2 = ((s * (s - 1)) / 2) % M;
      s3 = (((s * (s - 1)) % M) * ((inv6 * (s - 2)) % M)) % M;
      pw = aligned_pw[i];
      sx0 = (pw * 8) % M;
      sx1 = (((pw * s) % M) * 4) % M;
      sx2 = (((pw * s2) % M) * 4 + sx1) % M;
      sx3 = (((pw * s3) % M) * 6 + 3 * sx2 - 2 * sx1) % M;
      isq = (1ll * i * i) % M;
      av2A_ = (av2A_ * sx0 + av2 * sx1 + ((2 * sx1 * i) % M) * avA_ +
               ((2 * sx2 * i) % M) * av + ((sx2 * isq) % M) * A_ +
               ((sx3 * isq) % M) * count) %
              M;
      av2 = (av2 * sx0 + ((2 * av * i) % M) * sx1 + ((isq * sx2) % M) * count) %
            M;
      avA_ = (avA_ * sx0 + av * sx1 + ((i * A_) % M) * sx1 +
              ((i * sx2) % M) * count) %
             M;
      av = (av * sx0 + ((i * sx1) % M) * count) % M;
      A_ = (sx0 * A_ + sx1 * count) % M;
      count = (sx0 * count) % M;
      res[k] = (res[k] - res[i]) % M;
    }
    res[k] = (res[k] + (av2A_ - av2)) % M;
  }
  if (res[1] < 0) res[1] += M;
  printf("%lld\n", res[1]);
  return 0;
}