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;
const int A = 100000, MD = 998244353;
int kk[A + 1];
int pp[A + 1][6][6], aa[6][6], tt[6][6];
int uu_[6], vv_[6], *uu = uu_, *vv = vv_;
int kp[A + 1];
bool sq[A + 1];
void init(int *aa, int a0, int a1, int a2, int a3, int a4, int a5) {
  aa[0] = a0, aa[1] = a1, aa[2] = a2, aa[3] = a3, aa[4] = a4, aa[5] = a5;
}
void init(int aa[][6], int x) {
  int x2 = x * 2 % MD;
  int xx = (long long)x * x % MD;
  init(aa[0], 2, 1, x2, x2, xx, xx);
  init(aa[1], 0, 2, 0, x2, 0, xx);
  init(aa[2], 0, 0, 2, 1, x, x);
  init(aa[3], 0, 0, 0, 2, 0, x);
  init(aa[4], 0, 0, 0, 0, 2, 1);
  init(aa[5], 0, 0, 0, 0, 0, 2);
}
void mult(int aa[][6], int *uu, int *vv) {
  for (int i = 0; i < 6; i++) {
    long long v = 0;
    for (int j = 0; j < 6; j++) v += (long long)aa[i][j] * uu[j];
    vv[i] = v % MD;
  }
}
void mult(int aa[][6], int bb[][6], int cc[][6]) {
  for (int i = 0; i < 6; i++)
    for (int j = 0; j < 6; j++) {
      long long c = 0;
      for (int k = 0; k < 6; k++) c += (long long)aa[i][k] * bb[k][j];
      cc[i][j] = c % MD;
    }
}
void power(int aa[][6], int pp[][6], int tt[][6], int k) {
  if (k == 0) {
    for (int i = 0; i < 6; i++) {
      for (int j = 0; j < 6; j++) pp[i][j] = 0;
      pp[i][i] = 1;
    }
    return;
  }
  if (k & 1) {
    power(aa, pp, tt, k >> 1);
    mult(pp, pp, tt);
    mult(tt, aa, pp);
  } else {
    power(aa, tt, pp, k >> 1);
    mult(tt, tt, pp);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int m;
  cin >> m;
  while (m--) {
    int a, k;
    cin >> a >> k;
    kk[a] = k;
    init(aa, a);
    power(aa, pp[a], tt, k);
  }
  long long ans = 0;
  for (int a = 1; a <= A; a++) {
    if (sq[a]) continue;
    if (a > 1 && kp[a] == 0) {
      for (int b = a; b <= A; b += a) kp[b]++;
      if (a <= A / a)
        for (int s = a * a, t = s; t <= A; t += s) sq[t] = true;
    }
    fill(uu, uu + 6, 0);
    uu[5] = 1;
    for (int b = a; b <= A; b += a)
      if (kk[b] > 0) {
        mult(pp[b], uu, vv);
        swap(uu, vv);
      }
    int z = uu[0] - uu[1];
    ans += kp[a] % 2 == 0 ? z : -z;
  }
  ans %= MD;
  if (ans < 0) ans += MD;
  cout << ans << '\n';
  return 0;
}