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 bool upmin(T &x, T y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool upmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
const long double eps = 1e-11;
const long double pi = acos(-1);
const int oo = 1 << 30;
const long long loo = 1ll << 62;
const int mods = 998244353;
const int MAXN = 200005;
const int MX = 100000;
const int inv2 = (mods + 1) >> 1;
const int INF = 0x3f3f3f3f;
inline int read() {
  int f = 1, x = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + (c ^ 48);
    c = getchar();
  }
  return x * f;
}
int a[MAXN], flag[MAXN], mu[MAXN], prime[MAXN], f[MAXN], g[MAXN], s[MAXN],
    _s[MAXN], pnum = 0, num = 0;
int upd(int x, int y, int p = mods) { return x + y >= p ? x + y - p : x + y; }
int quick_pow(int x, int y) {
  if (y < 0) return 0;
  int ret = 1;
  for (; y; y >>= 1) {
    if (y & 1) ret = 1ll * ret * x % mods;
    x = 1ll * x * x % mods;
  }
  return ret;
}
void Init(int n) {
  flag[1] = mu[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!flag[i]) prime[++pnum] = i, mu[i] = -1;
    for (int j = 1; j <= pnum && prime[j] * i <= n; j++) {
      flag[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        mu[i * prime[j]] = 0;
        break;
      }
      mu[i * prime[j]] = -mu[i];
    }
  }
}
int solve() {
  int _s0 = 0, s0 = 0, s1 = 0, s2 = 0, sum = 0;
  for (int i = 1; i <= num; i++) {
    sum = upd(sum, upd(1ll * s1 * a[i] % mods * s[a[i]] % mods,
                       1ll * s[a[i]] * (s[a[i]] - 1) % mods * inv2 % mods *
                           a[i] % mods * a[i] % mods));
    s0 = upd(s0, s[a[i]]), _s0 = upd(_s0, _s[a[i]], mods - 1);
    s1 = upd(s1, 1ll * a[i] * s[a[i]] % mods);
    s2 = upd(s2, 1ll * a[i] * a[i] % mods * s[a[i]] % mods);
  }
  return upd(
      upd(1ll * s2 * (s0 + mods - 1) % mods * quick_pow(2, _s0 + mods - 3) %
              mods,
          1ll * sum * quick_pow(2, _s0 + mods - 2) % mods),
      1ll * sum * (s0 + mods - 2) % mods * quick_pow(2, _s0 + mods - 3) % mods);
}
signed main() {
  Init(100000);
  int n = read();
  for (int i = 1, x, y; i <= n; i++)
    x = read(), y = read(), s[x] = upd(s[x], y),
    _s[x] = upd(_s[x], y, mods - 1);
  for (int i = MX; i >= 1; i--) {
    num = 0;
    for (int j = i; j <= MX; j += i)
      if (s[j] || _s[j]) a[++num] = j;
    g[i] = (num ? solve() : 0);
    for (int j = 1; j <= MX / i; j++) {
      if (mu[j] == 1) f[i] = upd(f[i], g[i * j]);
      if (mu[j] == -1) f[i] = upd(f[i], mods - g[i * j]);
    }
  }
  printf("%d\n", f[1]);
  return 0;
}