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;
int M;
signed long long F[101010];
signed long long V[101010];
const signed long long mo = 998244353;
signed long long modpow(signed long long a, signed long long n = mo - 2) {
  signed long long r = 1;
  a %= mo;
  while (n) r = r * ((n % 2) ? a : 1) % mo, a = a * a % mo, n >>= 1;
  return r;
}
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> M;
  for (i = 0; i < (M); i++) {
    cin >> x >> y;
    V[x] = y;
  }
  for (i = 100000; i >= 1; i--) {
    signed long long S1 = 0, S2 = 0, N = 0;
    for (j = i; j <= 100000; j += i) {
      N += V[j];
      (S1 += V[j] * j) %= mo;
      (S2 += V[j] * j % mo * j) %= mo;
    }
    if (N >= 2) {
      F[i] += S2 * ((N - 1) % mo) % mo * modpow(2, N - 2);
      signed long long v = (S1 * S1 % mo + mo - S2) % mo;
      F[i] += v * modpow(2, N - 2);
      if (N >= 3) F[i] += v * ((N - 2) % mo) % mo * modpow(2, N - 3);
    }
    F[i] %= mo;
    for (j = i * 2; j <= 100000; j += i) F[i] -= F[j];
    F[i] = (F[i] % mo + mo) % mo;
  }
  cout << F[1] << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  cout.tie(0);
  solve();
  return 0;
}