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;
template <class streetdancer3>
void read(streetdancer3& x) {
  cin >> x;
}
template <class streetdancer3>
void read(vector<streetdancer3>& a) {
  for (auto& x : a) read(x);
}
const int nax = 998244353;
int mul(int x, int y) { return 1ll * x * y % nax; }
int expo(int a, int b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = mul(res, a);
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
const long long inv2 = expo(2, nax - 2), inv4 = expo(4, nax - 2),
                inv8 = expo(8, nax - 2);
const int mod = 1e9 + 7;
const int maxn = 1e5 + 100;
int primes[maxn], dp[maxn + 1][8];
void solve() {
  int n;
  cin >> n;
  while (n--) {
    int a, b;
    cin >> a >> b;
    int p = expo(2, b);
    dp[a][0] = p;
    dp[a][1] = dp[a][2] = (long long)a * b % nax * p % nax * inv2 % nax;
    dp[a][3] = ((long long)b * inv2 + (long long)b * (b - 1) % nax * inv4) %
               nax * a % nax * a % nax * p % nax;
    dp[a][4] = (long long)b * p % nax * inv2 % nax;
    dp[a][5] = dp[a][6] =
        ((long long)b * inv2 + (long long)b * (b - 1) % nax * inv4) % nax * a %
        nax * p % nax;
    dp[a][7] = ((long long)b * inv2 + 3ll * b % nax * (b - 1) % nax * inv4 +
                (long long)b * (b - 1) % nax * (b - 2) % nax * inv8) %
               nax * a % nax * a % nax * p % nax;
  }
  int res = 0;
  for (int i = 1; i < maxn + 1; i++) {
    for (int j = 2 * i; j <= maxn; j += i) {
      for (int second = 7; second >= 0; second--) {
        int val = 0;
        for (int t = second;; t = (t - 1) & second) {
          val = (val + (long long)(dp[i][t]) * dp[j][t ^ second]) % nax;
          if (t == 0) break;
        }
        dp[i][second] = val;
      }
    }
    res = (res + primes[i] * (dp[i][7] - dp[i][3])) % nax;
  }
  res = (res + nax) % nax;
  cout << res;
}
void precompute() {
  primes[1] = 1;
  for (int i = 1; i < maxn + 1; i++)
    for (int j = 2 * i; j <= maxn; j += i) primes[j] -= primes[i];
  for (int i = 1; i < maxn + 1; i++) dp[i][0] = 1;
}
int main() {
  precompute();
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}