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;
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void) {
  register bool f = false;
  register char ch =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
           ? EOF
           : *p1++);
  register int res = 0;
  while (!isdigit(ch))
    f |= (ch == '-'),
        ch = (p1 == p2 &&
                      (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
                  ? EOF
                  : *p1++);
  while (isdigit(ch))
    res = 10 * res + ch - '0',
    ch = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
              ? EOF
              : *p1++);
  return f ? -res : res;
}
const long long p = 998244353;
const int MAXN = 1e5 + 1;
long long A[MAXN];
long long pw(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = ret * a % p;
    a = a * a % p;
    b >>= 1;
  }
  return ret;
}
bool vis[MAXN];
int tot, prime[MAXN];
int mu[MAXN];
inline void Init(register int n) {
  mu[1] = 1;
  for (register int i = 2; i <= n; ++i) {
    if (!vis[i]) {
      prime[++tot] = i;
      mu[i] = -1;
    }
    for (register int j = 1; j <= tot && i * prime[j] <= n; ++j) {
      vis[i * prime[j]] = true;
      if (!(i % prime[j])) break;
      mu[i * prime[j]] = -mu[i];
    }
  }
  return;
}
int main(void) {
  Init(1e5);
  int m;
  cin >> m;
  while (m--) {
    int a, b;
    cin >> a >> b;
    A[a] = b;
  }
  long long ans = 0;
  for (register int i = 1; i < MAXN; ++i) {
    long long s = 0, sq = 0;
    long long K = 0;
    for (int j = i; j < MAXN; j += i) {
      K += A[j];
      s = (s + A[j] * j) % p;
      sq = (sq + A[j] * j % p * j) % p;
    }
    if (K < 2) continue;
    long long t1 = sq * pw(2, K - 2) % p * ((K - 1) % p) % p;
    long long n2 = (s * s + p - sq) % p;
    long long t2 = pw(2, K - 2);
    if (K >= 3) t2 = (t2 + ((K - 2) % p) * pw(2, K - 3)) % p;
    t2 = t2 * n2 % p;
    long long add = ((t1 + t2) % p * mu[i]);
    ans = (ans + (add + p)) % p;
  }
  printf("%lld\n", ans);
  return 0;
}