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 long long mod = 998244353;
long long qpow(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) {
      ret *= a;
      ret %= mod;
    }
    b >>= 1;
    a *= a;
    a %= mod;
  }
  return ret;
}
int v[100066];
vector<int> prime;
int mu[100066];
void init() {
  int N = 100000;
  for (int i = 2; i <= N; i++) {
    if (!v[i]) {
      mu[i] = 1;
      v[i] = i;
      prime.push_back(i);
    }
    for (auto p : prime) {
      if (p > v[i] || i > N / p) break;
      v[i * p] = p;
      if (i % p == 0)
        mu[i * p] = 0;
      else
        mu[i * p] = -mu[i];
    }
  }
}
long long solve(vector<pair<int, int> > vec) {
  long long sum = 0, all = 0;
  long long all1 = 0;
  for (auto x : vec) {
    sum = (sum + 1LL * x.first * x.second) % mod;
    all = (all + x.second) % mod;
    all1 = (all1 + x.second) % (mod - 1);
  }
  long long pp = ((all - 1) * qpow(2, all1 - 2 + mod - 1)) % mod;
  long long qq = (all % mod * qpow(2, all1 - 3 + mod - 1)) % mod;
  long long ret = 0;
  for (auto x : vec) {
    ret += pp * x.first % mod * x.first % mod * x.second % mod;
    ret %= mod;
    long long tmp = (sum + mod - x.first) % mod;
    tmp = 1ll * x.second * x.first % mod * tmp % mod * qq % mod;
    ret = (ret + tmp) % mod;
  }
  return ret;
}
int n;
vector<pair<int, int> > vec, V[100066];
int main() {
  init();
  scanf("%d", &n);
  int x, y;
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &x, &y);
    vec.push_back(make_pair(x, y));
    for (int j = 1; 1ll * j * j <= x; j++) {
      if (x % j) continue;
      V[j].push_back(make_pair(x, y));
      if (x / j != j) V[x / j].push_back(make_pair(x, y));
    }
  }
  long long ans = solve(vec);
  for (int i = 2; i <= 100000; i++) {
    long long tmp = (-solve(V[i]) * mu[i] + mod) % mod;
    ans = (ans + tmp) % mod;
  }
  printf("%lld\n", (ans + mod) % mod);
  return 0;
}