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 readint() {
  int x = 0;
  char c = getchar();
  bool f = 0;
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') {
    f = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return f ? -x : x;
}
const int maxm = 1e5 + 5;
int c[maxm];
const long long mod = 998244353;
const int S = 4e4;
long long pw1[maxm], pw2[maxm];
long long ksm(long long b) {
  b = (b % (mod - 1) + mod - 1) % (mod - 1);
  return pw1[b % S] * pw2[b / S] % mod;
}
int mf[maxm];
vector<int> p;
long long mu[maxm];
int main() {
  for (int i = 2; i < maxm; i++) {
    if (!mf[i]) p.push_back(i);
    for (int j = 0; j < (int)p.size() && 1ll * i * p[j] < maxm; j++) {
      mf[i * p[j]] = p[j];
      if (i % p[j] == 0) break;
    }
  }
  mu[1] = 1;
  for (int i = 2; i < maxm; i++)
    if (!mf[i])
      mu[i] = mod - 1;
    else {
      if (i / mf[i] % mf[i] == 0)
        mu[i] = 0;
      else
        mu[i] = mu[mf[i]] * mu[i / mf[i]] % mod;
    }
  pw1[0] = pw2[0] = 1;
  for (int i = 1; i <= S; i++) pw1[i] = pw1[i - 1] * 2 % mod;
  for (int i = 1; i <= S; i++) pw2[i] = pw2[i - 1] * pw1[S] % mod;
  int m = readint();
  while (m--) {
    int a = readint();
    c[a] = readint();
  }
  long long ans = 0;
  for (int i = 1; i < maxm; i++)
    if (mu[i]) {
      long long tot = 0;
      for (int j = i; j < maxm; j += i) tot += c[j];
      long long res = 0, s = 0;
      for (int j = i; j < maxm; j += i) {
        res = (res + (tot - 1 + mod) % mod * ksm(tot - 2) % mod * j % mod * j %
                         mod * c[j] % mod) %
              mod;
        res = (res + tot % mod * ksm(tot - 2) % mod * j % mod * s % mod * c[j] %
                         mod) %
              mod;
        res = (res + tot % mod * ksm(tot - 3) % mod * j % mod * j % mod * c[j] %
                         mod * (c[j] - 1) % mod) %
              mod;
        s = (s + 1ll * j * c[j] % mod) % mod;
      }
      ans = (ans + res * mu[i] % mod) % mod;
    }
  printf("%lld\n", ans);
  return 0;
}