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;
namespace Flandre_Scarlet {
long long I() {
  char c = getchar();
  long long x = 0;
  long long f = 1;
  while (c < '0' or c > '9') f = (c == '-') ? -1 : 1, c = getchar();
  while (c >= '0' and c <= '9')
    x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return ((f == 1) ? x : -x);
}
template <typename T>
void Rd(T &arg) {
  arg = I();
}
template <typename T, typename... Types>
void Rd(T &arg, Types &...args) {
  arg = I();
  Rd(args...);
}
void RA(long long *p, long long n) {
  for (long long i = 1; i <= n; ++i) *p = I(), ++p;
}
long long n, a[114514], f[114514];
void Input() {
  Rd(n);
  for (long long i = 1; i <= n; ++i) Rd(a[i], f[i]);
}
long long primes[114514];
bitset<114514> notp;
long long mu[114514];
void Init() {
  long long n = 1e5;
  notp[1] = 1;
  mu[1] = 1;
  long long &cnt = primes[0];
  for (long long i = 2; i <= n; ++i) {
    if (!notp[i]) primes[++cnt] = i, mu[i] = -1;
    for (long long j = 1; j <= cnt and i * primes[j] <= n; ++j) {
      long long u = primes[j];
      notp[i * u] = 1;
      if (i % u == 0) {
        mu[i * u] = 0;
        break;
      } else {
        mu[i * u] = -mu[i];
      }
    }
  }
}
long long qpow(long long a, long long b, long long m = 998244353) {
  if (b < 0) return 0;
  long long r = 1;
  while (b) {
    if (b & 1) r = r * a % m;
    a = a * a % m, b >>= 1;
  }
  return r;
}
long long sum, sum2, sumxy, nn;
long long s[114514], s2[114514], c[114514];
long long calc(long long d) {
  sum = sum2 = sumxy = nn = 0;
  for (long long i = d; i <= 100000; i += d) {
    nn = (nn + c[i]);
    sum = (sum + s[i]) % 998244353;
    sum2 = (sum2 + s2[i]) % 998244353;
  }
  sumxy = (sum * sum % 998244353 - sum2 % 998244353 + 998244353) % 998244353;
  long long part1 =
      sum2 * (nn % 998244353 - 1) % 998244353 * qpow(2, nn - 2) % 998244353;
  long long part2 =
      sumxy *
      ((nn % 998244353 - 2) * qpow(2, nn - 3) % 998244353 + qpow(2, nn - 2)) %
      998244353;
  long long ans = (part1 + part2) % 998244353;
  return ans;
}
void Soviet() {
  Init();
  for (long long i = 1; i <= n; ++i) {
    c[a[i]] = (c[a[i]] + f[i]);
    s[a[i]] = (s[a[i]] + a[i] * f[i] % 998244353) % 998244353;
    s2[a[i]] =
        (s2[a[i]] + a[i] * a[i] % 998244353 * f[i] % 998244353) % 998244353;
  }
  long long ans = 0;
  for (long long i = 1; i <= 100000; ++i) {
    ans = (ans + mu[i] * calc(i) % 998244353 + 998244353) % 998244353;
  }
  printf("%lld\n", ans);
}
void IsMyWife() {
  Input();
  Soviet();
}
}  // namespace Flandre_Scarlet
int main() {
  Flandre_Scarlet::IsMyWife();
  getchar();
  return 0;
}