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 N = 1e5 + 5;
const long long mod = 998244353;
long long bigmod(long long a, long long b) {
  long long ans = 1;
  while (b > 0) {
    if (b & 1) {
      ans = (ans * 1ll * a) % mod;
    }
    a = (a * 1ll * a) % mod;
    b >>= 1;
  }
  return ans;
}
inline long long add(long long x, long long y) { return (x + y) % mod; }
inline long long sub(long long x, long long y) {
  return (((x - y) % mod) + mod) % mod;
}
inline long long gun(long long x, long long y) { return ((x * 1ll * y) % mod); }
inline long long vag(long long x, long long y) {
  return (x * 1ll * bigmod(y, mod - 2)) % mod;
}
long long n;
vector<array<long long, 2> > a;
vector<array<long long, 2> > g[N];
long long sum1[N];
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  a.resize(n);
  for (long long i = 0; i < n; i++) {
    cin >> a[i][0] >> a[i][1];
    long long now = a[i][0];
    for (long long j = 1; j * j <= now; j++) {
      if (now % j == 0) {
        g[j].push_back(a[i]);
        if (j != (now / j)) {
          g[now / j].push_back(a[i]);
        }
      }
    }
  }
  for (long long i = 1; i < N; i++) {
    if (g[i].empty()) continue;
    long long koto = 0;
    for (long long j = 0; j < g[i].size(); j++) {
      koto += g[i][j][1];
    }
    long long sz = g[i].size();
    long long now = gun((koto - 1) % mod, bigmod(2, (koto - 2) % (mod - 1)));
    long long eta = 0;
    long long sum = 0;
    for (long long j = 0; j < g[i].size(); j++) {
      eta = add(eta, gun(g[i][j][0], gun(g[i][j][0], g[i][j][1])));
      sum = add(sum, gun(g[i][j][0], g[i][j][1]));
    }
    sum1[i] = gun(eta, now);
    if (koto <= 1) continue;
    now = add(gun((koto - 2) % mod, bigmod(2, (koto - 3) % (mod - 1))),
              bigmod(2, (koto - 2) % (mod - 1)));
    eta = 0;
    for (long long j = 0; j < g[i].size(); j++) {
      sum = sub(sum, g[i][j][0]);
      eta = add(eta, gun(g[i][j][1], gun(g[i][j][0], sum)));
      sum = add(sum, g[i][j][0]);
    }
    sum1[i] = add(sum1[i], gun(eta, now));
  }
  for (long long i = N - 1; i >= 1; i--) {
    for (long long j = i + i; j < N; j += i) {
      sum1[i] = sub(sum1[i], sum1[j]);
    }
  }
  cout << sum1[1] << "\n";
  return 0;
}