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;
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
  register int r = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9')
    r = (r << 1) + (r << 3) + (ch ^ 48), ch = getchar();
  return r;
}
int n, m, q, ans, pri[1000000], miu[1000000], bo[1000000], f[1000000],
    a[1000000];
void xxs(int n) {
  miu[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!bo[i]) {
      pri[++m] = i;
      miu[i] = -1;
    }
    for (int j = 1; j <= m && 1ll * pri[j] * i <= n; j++) {
      bo[pri[j] * i] = 1;
      if (i % pri[j] == 0) break;
      miu[i * pri[j]] = -miu[i];
    }
  }
}
inline void mo(int &x) {
  if (x >= 998244353) x -= 998244353;
  if (x < 0) x += 998244353;
}
inline int kp(int a, int b) {
  int c = 1;
  while (b > 0) {
    if (b & 1) c = 1ll * c * a % 998244353;
    a = 1ll * a * a % 998244353;
    b >>= 1;
  }
  return c;
}
int main() {
  xxs(100005);
  n = read();
  for (int i = 1, x; i <= n; i++) x = read(), a[x] += read(), q = max(q, x);
  for (int i = 1; i <= q; i++) {
    int ans = 0, s = 0;
    long long sum = 0;
    for (int j = i; j <= q; j += i)
      sum += a[j], mo(s += 1ll * j * a[j] % 998244353);
    if (sum < 2) continue;
    int x = kp(2, (sum - 2) % (998244353 - 1)),
        y = kp(2, (sum - 3) % (998244353 - 1));
    sum %= 998244353;
    for (int j = i; j <= q; j += i)
      mo(ans +=
         (1ll * j * j % 998244353 * a[j] % 998244353 *
              (1ll * (sum - 1 + 998244353) * x % 998244353 +
               1ll * (a[j] - 1 + 998244353) *
                   (1ll * (sum - 2 + 998244353) % 998244353 * y % 998244353 +
                    x) %
                   998244353) %
              998244353 +
          1ll * j * a[j] % 998244353 *
              (s - 1ll * j * a[j] % 998244353 + 998244353) % 998244353 *
              (1ll * (sum - 2 + 998244353) % 998244353 * y % 998244353 + x) %
              998244353) %
         998244353);
    f[i] = ans;
  }
  for (int i = 1; i <= q; i++)
    if (miu[i]) mo(ans += miu[i] * f[i]);
  printf("%d", ans);
  return 0;
}