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 <typename T>
inline void ckmax(T& x, T y) {
  x = (y > x ? y : x);
}
template <typename T>
inline void ckmin(T& x, T y) {
  x = (y < x ? y : x);
}
const int MAXN = 1e5;
const int MOD = 998244353;
inline int mod1(int x) { return x < MOD ? x : x - MOD; }
inline int mod2(int x) { return x < 0 ? x + MOD : x; }
inline void add(int& x, int y) { x = mod1(x + y); }
inline void sub(int& x, int y) { x = mod2(x - y); }
inline int pow_mod(int x, int i) {
  int y = 1;
  while (i) {
    if (i & 1) y = (long long)y * x % MOD;
    x = (long long)x * x % MOD;
    i >>= 1;
  }
  return y;
}
int p[MAXN + 5], cnt_p, mu[MAXN + 5];
bool v[MAXN + 5];
void sieve(int lim = MAXN) {
  mu[1] = 1;
  for (int i = 2; i <= lim; ++i) {
    if (!v[i]) {
      p[++cnt_p] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= cnt_p && p[j] * i <= lim; ++j) {
      v[i * p[j]] = 1;
      if (i % p[j] == 0) {
        break;
      }
      mu[i * p[j]] = -mu[i];
    }
  }
}
int n, m, freq[MAXN + 5];
int f[MAXN + 5];
int main() {
  sieve(n = MAXN);
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    int a;
    cin >> a;
    cin >> freq[a];
  }
  for (int i = 1; i <= n; ++i) {
    long long tot = 0;
    for (int j = i; j <= n; j += i) {
      tot += freq[j];
    }
    if (tot < 2) continue;
    int w2, w3;
    w3 = pow_mod(2, (tot - 2) % (MOD - 1));
    w2 = (long long)(tot - 1) % MOD * w3 % MOD;
    if (tot >= 3)
      w3 = ((long long)w3 +
            (long long)(tot - 2) % MOD * pow_mod(2, (tot - 3) % (MOD - 1))) %
           MOD;
    for (int j = i; j <= n; j += i)
      if (freq[j]) {
        f[i] = ((long long)f[i] + (long long)j * j % MOD * w2 % MOD * freq[j]) %
               MOD;
        if (freq[j] >= 2) {
          f[i] = ((long long)f[i] + (long long)j * j % MOD * w3 % MOD *
                                        freq[j] % MOD * (freq[j] - 1)) %
                 MOD;
        }
      }
    int sum = 0;
    for (int j = i; j <= n; j += i)
      if (freq[j]) {
        sum = ((long long)sum + (long long)j * freq[j]) % MOD;
      }
    for (int j = i; j <= n; j += i)
      if (freq[j]) {
        int cur = mod2(sum - (long long)j * freq[j] % MOD);
        f[i] =
            ((long long)f[i] + (long long)j * freq[j] % MOD * cur % MOD * w3) %
            MOD;
      }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (mu[i] == 1) add(ans, f[i]);
    if (mu[i] == -1) sub(ans, f[i]);
  }
  cout << ans << endl;
  return 0;
}