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>
void mult(int aa[][6], int bb[][6], int cc[][6]) {
  static long long cc_[6][6];
  int i, j, k;
  for (i = 0; i < 6; i++)
    for (j = i; j < 6; j++) cc_[i][j] = 0;
  for (i = 0; i < 6; i++) {
    int *ai = aa[i];
    for (k = i; k < 6; k++) {
      int *bk = bb[k], a = ai[k];
      if (a != 0)
        for (j = k; j < 6; j++) {
          int b = bk[j];
          if (b != 0) cc_[i][j] += (long long)a * b;
        }
    }
  }
  for (i = 0; i < 6; i++)
    for (j = i; j < 6; j++) cc[i][j] = cc_[i][j] % 998244353;
}
void power(int aa[][6], int pp[][6], int tt[][6], int k) {
  if (k == 0) {
    int i, j;
    for (i = 0; i < 6; i++)
      for (j = 0; j < 6; j++) pp[i][j] = i == j;
    return;
  }
  if (k % 2 == 0) {
    power(aa, tt, pp, k / 2);
    mult(tt, tt, pp);
  } else {
    power(aa, pp, tt, k / 2);
    mult(pp, pp, tt);
    mult(tt, aa, pp);
  }
}
int main() {
  static int dp[100000 + 1][6];
  int n, a, b;
  scanf("%d", &n);
  for (a = 0; a <= 100000; a++) dp[a][5] = 1;
  while (n--) {
    static int aa[6][6], pp[6][6], tt[6][6];
    int k, i, j;
    scanf("%d%d", &a, &k);
    aa[0][0] = 2, aa[0][1] = 1, aa[0][2] = a * 2 % 998244353,
    aa[0][4] = (long long)a * a % 998244353;
    aa[1][1] = 2, aa[1][3] = a * 2 % 998244353,
    aa[1][5] = (long long)a * a % 998244353;
    aa[2][2] = 2, aa[2][3] = 1, aa[2][4] = a, aa[2][5] = a;
    aa[3][3] = 2, aa[3][5] = a;
    aa[4][4] = 2, aa[4][5] = 1;
    aa[5][5] = 2;
    power(aa, pp, tt, k);
    for (b = 1; b <= a / b; b++)
      if (a % b == 0) {
        for (i = 0; i < 6; i++) {
          long long x;
          x = 0;
          for (j = i; j < 6; j++) x += (long long)pp[i][j] * dp[b][j];
          dp[b][i] = x % 998244353;
        }
        if (b != a / b)
          for (i = 0; i < 6; i++) {
            long long x;
            x = 0;
            for (j = i; j < 6; j++) x += (long long)pp[i][j] * dp[a / b][j];
            dp[a / b][i] = x % 998244353;
          }
      }
  }
  for (a = 100000; a > 0; a--)
    for (b = a + a; b <= 100000; b += a)
      if ((dp[a][0] -= dp[b][0]) < 0) dp[a][0] += 998244353;
  printf("%d\n", dp[1][0]);
  return 0;
}