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;
const int N = 100005;
const int mo = 998244353;
int w0[N], wo[N], w1[N], w2[N];
int n, ans[N];
int power(int x, int y) {
  int s = 1;
  if (y < 0) y += mo - 1;
  for (; y; y /= 2, x = 1ll * x * x % mo)
    if (y & 1) s = 1ll * s * x % mo;
  return s;
}
int main() {
  scanf("%d", &n);
  for (int i = (int)(1); i <= (int)(n); i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    w0[x] = (w0[x] + y) % (mo - 1);
    wo[x] = (wo[x] + y) % mo;
    w1[x] = (w1[x] + 1ll * x * y) % mo;
    w2[x] = (w2[x] + 1ll * x * x % mo * y) % mo;
  }
  for (int i = (int)(1); i <= (int)(N - 1); i++)
    for (int j = (int)(2); j <= (int)((N - 1) / i); j++) {
      w0[i] = (w0[i] + w0[i * j]) % (mo - 1);
      wo[i] = (wo[i] + wo[i * j]) % mo;
      w1[i] = (w1[i] + w1[i * j]) % mo;
      w2[i] = (w2[i] + w2[i * j]) % mo;
    }
  for (int i = (int)(1); i <= (int)(N - 1); i++) {
    ans[i] = 1ll * power(2, w0[i] - 2) * (wo[i] + mo - 1) % mo * w2[i] % mo;
    ans[i] = (ans[i] + (1ll * power(2, w0[i] - 3) * (wo[i] + mo - 2) +
                        power(2, w0[i] - 2)) %
                           mo * (1ll * w1[i] * w1[i] % mo + mo - w2[i])) %
             mo;
  }
  for (int i = (int)(N - 1); i >= (int)(1); i--)
    for (int j = (int)(2); j <= (int)((N - 1) / i); j++)
      ans[i] = (ans[i] + mo - ans[i * j]) % mo;
  cout << ans[1] << endl;
}