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>
constexpr int N = 1e5, P = 998244353;
int power(int a, int b) {
  int res = 1;
  for (; b; b /= 2, a = int64_t(a) * a % P)
    if (b & 1) res = int64_t(res) * a % P;
  return res;
}
const int Inv2 = power(2, P - 2), Inv4 = power(4, P - 2),
          Inv8 = power(8, P - 2);
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin >> n;
  int mu[N + 1] = {};
  mu[1] = 1;
  for (int i = 1; i <= N; ++i)
    for (int j = 2 * i; j <= N; j += i) mu[j] -= mu[i];
  int f[N + 1][8] = {};
  for (int i = 1; i <= N; ++i) f[i][0] = 1;
  while (n--) {
    int a, b;
    std::cin >> a >> b;
    int p = power(2, b);
    f[a][0] = p;
    f[a][1] = f[a][2] = int64_t(a) * b % P * p % P * Inv2 % P;
    f[a][3] = (int64_t(b) * Inv2 + int64_t(b) * (b - 1) % P * Inv4) % P * a %
              P * a % P * p % P;
    f[a][4] = int64_t(b) * p % P * Inv2 % P;
    f[a][5] = f[a][6] = (int64_t(b) * Inv2 + int64_t(b) * (b - 1) % P * Inv4) %
                        P * a % P * p % P;
    f[a][7] = (int64_t(b) * Inv2 + 3ll * b % P * (b - 1) % P * Inv4 +
               int64_t(b) * (b - 1) % P * (b - 2) % P * Inv8) %
              P * a % P * a % P * p % P;
  }
  int ans = 0;
  for (int i = 1; i <= N; ++i) {
    for (int j = 2 * i; j <= N; j += i) {
      for (int s = 7; s >= 0; --s) {
        int res = 0;
        for (int t = s;; t = (t - 1) & s) {
          res = (res + int64_t(f[i][t]) * f[j][t ^ s]) % P;
          if (t == 0) break;
        }
        f[i][s] = res;
      }
    }
    ans = (ans + mu[i] * (f[i][7] - f[i][3])) % P;
  }
  ans = (ans + P) % P;
  std::cout << ans << "\n";
  return 0;
}