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;
inline long long read() {
  char c = getchar();
  long long x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
struct modint {
  long long x;
  modint(long long o = 0) { x = o; }
  modint &operator=(long long o) { return x = o, *this; }
  modint &operator+=(modint o) {
    return x = x + o.x >= 998244353 ? x + o.x - 998244353 : x + o.x, *this;
  }
  modint &operator-=(modint o) {
    return x = x - o.x < 0 ? x - o.x + 998244353 : x - o.x, *this;
  }
  modint &operator*=(modint o) { return x = 1ll * x * o.x % 998244353, *this; }
  modint &operator^=(long long b) {
    if (b < 0) return x = 0, *this;
    b %= 998244353 - 1;
    modint a = *this, c = 1;
    for (; b; b >>= 1, a *= a)
      if (b & 1) c *= a;
    return x = c.x, *this;
  }
  modint &operator/=(modint o) { return *this *= o ^= 998244353 - 2; }
  modint &operator+=(long long o) {
    return x = x + o >= 998244353 ? x + o - 998244353 : x + o, *this;
  }
  modint &operator-=(long long o) {
    return x = x - o < 0 ? x - o + 998244353 : x - o, *this;
  }
  modint &operator*=(long long o) { return x = 1ll * x * o % 998244353, *this; }
  modint &operator/=(long long o) {
    return *this *= ((modint(o)) ^= 998244353 - 2);
  }
  template <class I>
  friend modint operator+(modint a, I b) {
    return a += b;
  }
  template <class I>
  friend modint operator-(modint a, I b) {
    return a -= b;
  }
  template <class I>
  friend modint operator*(modint a, I b) {
    return a *= b;
  }
  template <class I>
  friend modint operator/(modint a, I b) {
    return a /= b;
  }
  friend modint operator^(modint a, long long b) { return a ^= b; }
  friend bool operator==(modint a, long long b) { return a.x == b; }
  friend bool operator!=(modint a, long long b) { return a.x != b; }
  bool operator!() { return !x; }
  modint operator-() { return x ? 998244353 - x : 0; }
};
inline modint qpow(modint a, long long b) {
  if (b < 0) return 0;
  modint res = 1;
  for (; b; b >>= 1, a *= a)
    if (b & 1) res *= a;
  return res;
}
long long n, m;
modint f[400005];
long long s0[400005];
modint s1[400005], s2[400005];
signed main() {
  n = read();
  for (register long long i = (1); i <= (n); ++i) {
    modint a = read(), w = read();
    long long u = a.x;
    m = max(m, u);
    s0[u] = w.x, s1[u] = a * w, s2[u] = a * a * w;
  }
  for (register long long i = (1); i <= (m); ++i)
    for (long long j = i * 2; j <= m; j += i)
      s0[i] += s0[j], s1[i] += s1[j], s2[i] += s2[j];
  for (register long long i = (1); i <= (m); ++i) {
    long long cnt = s0[i];
    modint B = 2;
    if (cnt <= 1) continue;
    f[i] += (s1[i] * s1[i] - s2[i]) *
            (qpow(2, cnt - 2) + qpow(2, cnt - 3) * (cnt % 998244353 - 2));
    f[i] += s2[i] * (qpow(2, cnt - 2) * (cnt % 998244353 - 1));
  }
  for (register long long i = (m); i >= (1); --i)
    for (long long j = i * 2; j <= m; j += i) f[i] -= f[j];
  cout << f[1].x;
  return 0;
}