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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
template <class T>
class _Fenwick {
 private:
  std::vector<T> sum;
  long long _size;

 public:
  _Fenwick() { _size = 0; }
  void reset(long long n) {
    _size = n;
    sum.clear();
    sum.resize(n + 1);
  }
  void add(long long x, T y) {
    while (x <= _size) {
      sum[x] += y;
      x += x & -x;
    }
  }
  T query(long long x, T y) {
    T ans = y;
    while (x) {
      ans += sum[x];
      x -= x & -x;
    };
    return ans;
  }
  void build(T *a, long long n) {
    reset(n);
    for (long long i = 1; i <= n; ++i) add(i, a[i]);
  }
};
template <typename T>
void read(T &x);
template <typename T>
void read(T &x, T &y);
template <typename T>
void read(T &x, T &y, T &z);
template <typename T>
void write(T x);
template <typename T>
void writeC(T x);
template <typename T>
void writeN(T x);
template <typename T>
void _binary(T x, long long len);
long long _qpow(long long a, long long b, long long M);
long long _inv(long long x, long long M);
const long long lim = 1e5;
const long long mod = 998244353;
long long mu[1000005], prime[1000005], tl, not_prime[1000005], m, x;
long long c[1000005];
void sieve() {
  mu[1] = 1;
  for (long long i = 2; i <= lim; ++i) {
    if (!not_prime[i]) {
      prime[++tl] = i;
      mu[i] = mod - 1;
    }
    for (long long j = 1; j <= tl && i * prime[j] <= lim; ++j) {
      not_prime[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        mu[i * prime[j]] = 0;
        break;
      } else
        mu[i * prime[j]] = mod - mu[i];
    }
  }
}
long long W1, W2;
long long f(long long n) {
  if (n == 0) return 0;
  return (long long)n % mod * W1 % mod;
}
long long f2(long long n) {
  if (n == 0) return 1;
  return (long long)(n + 2) % mod * W2 % mod;
}
long long F(long long s, long long c) {
  if (!c) return 0;
  return (long long)s * f2(c - 1) % mod;
}
long long calc(long long d) {
  std::vector<std::pair<long long, long long> > v;
  long long sum = 0, ans = 0;
  long long cnt = 0;
  for (long long i = d; i <= lim; i += d) {
    if (c[i]) {
      v.push_back(std::make_pair(i, c[i]));
      sum = (sum + (long long)i * c[i] % mod) % mod;
      cnt = (cnt + c[i]);
    }
  }
  long long c1 = cnt - 1;
  if (c1 <= 0) return 0;
  W1 = _qpow(2, c1 - 1, mod);
  if (c1 - 2 >= 0) W2 = _qpow(2, c1 - 2, mod);
  for (auto x : v) {
    long long a = x.first, c = x.second;
    long long s1 = (sum - a + mod) % mod;
    if (!c1) continue;
    long long d = (F(s1, c1) + (long long)a * f(c1) % mod) % mod;
    ans = (ans + (long long)c % mod * a % mod * d % mod) % mod;
  }
  return ans;
}
signed main() {
  sieve();
  read(m);
  for (long long i = (1); i <= (m); ++i) {
    read(x);
    assert(!c[x]);
    read(c[x]);
  }
  long long ans = 0;
  for (long long d = 1; d <= lim; ++d) {
    ans = (ans + (long long)mu[d] * calc(d) % mod) % mod;
  }
  writeC(ans);
  return 0;
}
template <typename T>
void read(T &x) {
  x = 0;
  char c = getchar();
  T flag = 1;
  while (c < '0' || c > '9') {
    if (c == '-') flag = -flag;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= flag;
}
template <typename T>
void read(T &x, T &y) {
  read(x);
  read(y);
}
template <typename T>
void read(T &x, T &y, T &z) {
  read(x);
  read(y);
  read(z);
}
template <typename T>
void writeC(T x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) writeC(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void write(T x) {
  writeC(x);
  putchar(' ');
}
template <typename T>
void writeN(T x) {
  writeC(x);
  puts("");
}
template <typename T>
void _binary(T x, long long len) {
  for (long long i = len - 1; i >= 0; --i) writeC((x >> i) & 1);
}
long long _inv(long long x, long long M) {
  assert(x != 0);
  return x == 1 ? 1 : (M - M / x) * _inv(M % x, M) % M;
}
long long _qpow(long long a, long long b, long long M) {
  assert(0 <= b);
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % M;
    a = a * a % M;
    b >>= 1;
  }
  return res;
}