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 int N = 1e5 + 5, mod = 998244353;
template <class o>
inline void qr(o &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + (c ^ 48);
    c = getchar();
  }
  x *= f;
}
template <class o>
void qw(o x) {
  if (x / 10) qw(x / 10);
  putchar(x % 10 + 48);
}
template <class o>
void pr1(o x) {
  if (x < 0) putchar('-'), x = -x;
  qw(x);
  putchar(' ');
}
template <class o>
void pr2(o x) {
  if (x < 0) putchar('-'), x = -x;
  qw(x);
  puts("");
}
inline int ksm(int a, long long b = mod - 2) {
  int ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) ans = 1ll * ans * a % mod;
  return ans;
}
inline int add(int a, int b) { return a += b, a >= mod ? a - mod : a; }
inline int sub(int a, int b) { return a -= b, a < 0 ? a + mod : a; }
int s[N], s1[N], s2[N];
int f[N];
long long cnt[N];
void upd(int i, int sum, int sum1, int sum2, int c) {
  s2[i] = add(s2[i], (sum2 + 2ll * sum * s[i]) % mod);
  s[i] = add(s[i], sum);
  s1[i] = add(s1[i], sum1);
  cnt[i] += c;
}
void solve() {
  int m;
  qr(m);
  int n = 1e5;
  for (int i = 1; i <= m; ++i) {
    int x, f;
    qr(x), qr(f);
    int sum = 1ll * x * f % mod;
    int sum1 = 1ll * x * x % mod * f % mod;
    int sum2 = 1ll * x * x % mod * (f - 1) % mod * f % mod;
    for (int j = 1; j * j <= x; ++j) {
      if (x % j) continue;
      upd(j, sum, sum1, sum2, f);
      if (x / j != j) upd(x / j, sum, sum1, sum2, f);
    }
  }
  for (int i = n; i; --i)
    if (cnt[i]) {
      long long k = cnt[i];
      int &res = f[i];
      int p2 = 0, p3 = 0;
      if (k > 2) {
        p3 = ksm(2, k - 3);
        p2 = p3 * 2 % mod;
      } else if (k > 1)
        p2 = ksm(2, k - 2);
      if (k > 1) {
        res = add(res, p2 * ((k - 1) % mod) % mod * s1[i] % mod);
        res = add(res, 1ll * p2 * s2[i] % mod);
      }
      if (k > 2) {
        res = add(res, p3 * ((k - 2) % mod) % mod * s2[i] % mod);
      }
      for (int j = 2 * i; j <= n; j += i) res = add(res, mod - f[j]);
    }
  pr2(f[1]);
}
int main() {
  solve();
  return 0;
}