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>
template <typename T>
inline void rd(T& x) {
  int si = 1;
  char c = getchar();
  x = 0;
  while (!isdigit(c)) si = c == '-' ? -1 : si, c = getchar();
  while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
  x *= si;
}
template <typename T, typename... Args>
inline void rd(T& x, Args&... args) {
  rd(x);
  rd(args...);
}
const int kN = 1e5 + 5, kInf = 0x3f3f3f3f;
const long long kMod = 998244353, kInfLL = 0x3f3f3f3f3f3f3f3fLL;
long long QPow(long long a, long long b) {
  if (b < 0) {
    a = QPow(a, kMod - 2);
    b = -b;
  }
  long long ret = 1, bas = a;
  for (; b; b >>= 1, bas = bas * bas % kMod)
    if (b & 1) ret = ret * bas % kMod;
  return ret;
}
int p[kN], mu[kN], cnt = 0;
bool is_p[kN];
void Sieve() {
  memset(is_p, true, sizeof(is_p));
  mu[1] = 1;
  is_p[1] = false;
  for (int i = 2; i < kN; ++i) {
    if (is_p[i]) {
      p[++cnt] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= cnt && i * p[j] < kN; ++j) {
      is_p[i * p[j]] = false;
      if (i % p[j] == 0) {
        mu[i * p[j]] = 0;
        break;
      }
      mu[i * p[j]] = -mu[i];
    }
  }
}
int n;
long long c1[kN], c2[kN], siz[kN];
int main() {
  int T = 1;
  Sieve();
  while (T--) {
    rd(n);
    for (int i = 1; i <= n; ++i) {
      long long x, freq;
      rd(x, freq);
      for (long long j = 1; j * j <= x; ++j)
        if (x % j == 0) {
          siz[j] += freq;
          c1[j] = (c1[j] + x * freq) % kMod;
          c2[j] = (c2[j] + x * x % kMod * freq) % kMod;
          if (j * j != x) {
            siz[x / j] += freq;
            c1[x / j] = (c1[x / j] + x * freq) % kMod;
            c2[x / j] = (c2[x / j] + x * x % kMod * freq) % kMod;
          }
        }
    }
    long long ans = 0;
    for (int i = 1; i < kN; ++i)
      if (siz[i] > 1) {
        ans = (ans +
               mu[i] *
                   ((c1[i] * c1[i] % kMod - c2[i]) % kMod *
                        ((QPow(2, siz[i] - 2) +
                          (siz[i] - 2) % kMod * QPow(2, siz[i] - 3) % kMod) %
                         kMod) %
                        kMod +
                    c2[i] * ((siz[i] - 1) % kMod * QPow(2, siz[i] - 2) % kMod) %
                        kMod) %
                   kMod +
               kMod) %
              kMod;
      }
    printf("%lld\n", ans);
  }
  return 0;
}