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;
vector<pair<long long, long long> > elem[100010];
long long nr[100010], f[100010];
long long dp[100010][3];
long long ridput(long long x, long long y) {
  long long sol = 1;
  if (y < 0) return 0;
  while (y) {
    if (y % 2) sol = (sol * x) % 998244353;
    x = (x * x) % 998244353;
    y /= 2;
  }
  return sol;
}
long long solve(long long n) {
  long long sol, i, tot = 0, x, frq, sum = 0, p2, cst, val;
  for (i = 0; i < elem[n].size(); i++) {
    tot = (tot + elem[n][i].first * elem[n][i].second) % 998244353;
    sum = sum + elem[n][i].second;
  }
  if (sum < 2) return 0;
  p2 = ridput(2, sum - 2);
  sol = 0;
  for (i = 0; i < elem[n].size(); i++) {
    x = elem[n][i].first;
    frq = elem[n][i].second;
    sol = (sol + (((x * x) % 998244353 * frq) % 998244353)) % 998244353;
  }
  sol = ((sol * p2) % 998244353 * ((sum - 1) % 998244353)) % 998244353;
  cst = ((((sum - 2) % 998244353) * ridput(2, sum - 3)) % 998244353 +
         ridput(2, sum - 2)) %
        998244353;
  val = 0;
  for (i = 0; i < elem[n].size(); i++) {
    x = elem[n][i].first;
    frq = elem[n][i].second;
    val = (val + ((x * (tot - x)) % 998244353 * frq) % 998244353) % 998244353;
  }
  cst = (cst * val) % 998244353;
  return (sol + cst) % 998244353;
}
int main() {
  FILE *fin = stdin;
  FILE *fout = stdout;
  long long n, i, x, y, d, sol, tot, p, aux;
  fscanf(fin, "%lld", &n);
  for (i = 1; i <= n; i++) {
    fscanf(fin, "%lld%lld", &x, &y);
    if (x != 1) elem[x].push_back(make_pair(x, y));
    elem[1].push_back(make_pair(x, y));
    d = 2;
    while (d * d <= x) {
      if (x % d == 0) {
        elem[d].push_back(make_pair(x, y));
        if (d != x / d) elem[x / d].push_back(make_pair(x, y));
      }
      d++;
    }
  }
  for (i = 2; i <= 100000; i++) {
    d = 2;
    tot = 0;
    aux = i;
    while (d * d <= aux) {
      if (aux % d == 0) {
        p = 0;
        while (aux % d == 0) {
          p++;
          aux /= d;
        }
        if (p == 1)
          tot++;
        else {
          d = -1;
          break;
        }
      }
      d++;
    }
    if (d != -1) {
      if (aux != 1) tot++;
      nr[i] = tot;
    }
  }
  sol = solve(1);
  for (i = 2; i <= 100000; i++) {
    if (nr[i] % 2 == 1)
      sol = (sol - solve(i)) % 998244353;
    else if (nr[i])
      sol = (sol + solve(i)) % 998244353;
  }
  if (sol < 0) sol += 998244353;
  fprintf(fout, "%lld", sol);
  return 0;
}