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 int read() {
  register int res = 0;
  register char c = getchar(), f = 1;
  while (c < 48 || c > 57) {
    if (c == '-') f = 0;
    c = getchar();
  }
  while (c >= 48 && c <= 57)
    res = (res << 3) + (res << 1) + (c & 15), c = getchar();
  return f ? res : -res;
}
inline void write(int x) {
  register char c[21], len = 0;
  if (!x) return putchar('0'), void();
  if (x < 0) x = -x, putchar('-');
  while (x) c[++len] = x % 10, x /= 10;
  while (len) putchar(c[len--] + 48);
}
const int mod = 998244353;
struct M {
  int x;
  inline M(int a = 0) : x(a) {}
  inline M operator+(const M& p) const {
    return x + p.x >= mod ? x + p.x - mod : x + p.x;
  }
  inline M operator-() const { return x ? mod - x : 0; }
  inline M operator-(const M& p) const {
    return x - p.x < 0 ? x - p.x + mod : x - p.x;
  }
  inline M operator*(const M& p) const { return (long long)x * p.x % mod; }
  inline bool operator==(const int& p) const { return x == p; }
  inline void operator+=(const M& p) { *this = *this + p; }
  inline void operator-=(const M& p) { *this = *this - p; }
  inline void operator*=(const M& p) { *this = *this * p; }
};
inline void write(const M& x) { write(x.x); }
inline M qpow(M x, long long y) {
  if (y < 0) return 0;
  M res = 1;
  for (; y; y >>= 1) y & 1 ? (res = res * x) : 1, x *= x;
  return res;
}
inline M inv(M x) { return qpow(x, mod - 2); }
const int N = 1e5 + 10;
int n, m, x, y;
long long s0[N];
M s, s1[N], s2[N], f[N];
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    x = read(), y = read(), s = x, m = max(m, x);
    s0[x] += y, s1[x] += s * y, s2[x] += s * s * y;
  }
  for (int i = 1; i <= m; ++i)
    for (int j = i * 2; j <= m; j += i)
      s0[i] += s0[j], s1[i] += s1[j], s2[i] += s2[j];
  for (int i = 1; i <= m; ++i)
    if (s0[i] > 1) {
      s = M(s0[i] % mod);
      f[i] = s2[i] * (s - 1) * qpow(2, s0[i] - 2) +
             (s1[i] * s1[i] - s2[i]) *
                 ((s - 2) * qpow(2, s0[i] - 3) + qpow(2, s0[i] - 2));
    }
  for (int i = m; i; --i)
    for (int j = i * 2; j <= m; j += i) f[i] -= f[j];
  write(f[1]), putchar('\n');
}