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>
const int mod = 998244353;
using namespace std;
int n, m, k, q, p, T, s[3][100010], f[100010];
long long cnt[100010];
int qmo(int x) { return x + ((x >> 31) & mod); }
int ksm(int a, long long k) {
  if (k < 0) return 0;
  int res = 1;
  for (; k; k >>= 1, a = 1ll * a * a % mod)
    if (k & 1) res = 1ll * res * a % mod;
  return res;
}
int main() {
  scanf("%d", &n);
  for (int i = 1, a, w; i <= n; i++) {
    scanf("%d%d", &a, &w);
    cnt[a] += w;
    s[1][a] = (s[1][a] + 1ll * a * w) % mod;
    s[2][a] = (s[2][a] + 1ll * a * a % mod * w) % mod;
  }
  for (int i = 1; i <= 100000; i++) {
    for (int j = 2 * i; j <= 100000; j += i) {
      cnt[i] += cnt[j];
      s[1][i] = qmo(s[1][i] + s[1][j] - mod);
      s[2][i] = qmo(s[2][i] + s[2][j] - mod);
    }
  }
  for (int i = 1; i <= 100000; i++) {
    if (cnt[i] <= 1) continue;
    f[i] =
        (1ll * qmo(1ll * s[1][i] * s[1][i] % mod - s[2][i]) *
             qmo(ksm(2, cnt[i] - 2) +
                 1ll * ksm(2, cnt[i] - 3) * qmo(cnt[i] % mod - 2) % mod - mod) +
         1ll * s[2][i] * ksm(2, cnt[i] - 2) % mod * qmo(cnt[i] % mod - 1)) %
        mod;
  }
  for (int i = 100000; i >= 1; i--) {
    for (int j = 2 * i; j <= 100000; j += i) {
      f[i] = qmo(f[i] - f[j]);
    }
  }
  printf("%d\n", f[1]);
}