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;
const int maxn = 100005;
const int mod = 998244353;
int n, m, i, j, t, k, s, mx, su[maxn], miu[maxn], pr[maxn], tot, jian[maxn];
long long ct[maxn];
bool vis[maxn];
inline int Pow(int x, long long y, int mo) {
  int ret = 1;
  while (y > 0) {
    if (y & 1) ret = 1ll * ret * x % mo;
    x = 1ll * x * x % mo;
    y >>= 1;
  }
  return ret;
}
inline int g(long long x) {
  if (x == 0) return 1;
  int tmp = Pow(2, x - 1ll, mod);
  return 1ll * (x + 2ll) % mod * tmp % mod;
}
inline int h(long long x) {
  return x == 0 ? 0 : x % mod * 1ll * Pow(2, x - 1, mod) % mod;
}
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) {
    scanf("%d%d", &t, &k);
    for (j = 1; 1ll * j * j <= t; ++j)
      if (t % j == 0) {
        su[j] = (su[j] + t * 1ll * k) % mod;
        ct[j] = (ct[j] + k * 1ll);
        jian[j] = (jian[j] + 1ll * t * t % mod * k) % mod;
        if (1ll * j * j != t) {
          su[t / j] = (su[t / j] + t * 1ll * k % mod) % mod;
          ct[t / j] = (ct[t / j] + k * 1ll);
          jian[t / j] = (jian[t / j] + 1ll * t * t % mod * k) % mod;
        }
      }
    mx = max(mx, t);
  }
  s = 0;
  miu[1] = 1;
  for (i = 1; i <= mx; ++i) {
    if (i != 1 && !vis[i]) {
      miu[i] = -1;
      pr[++tot] = i;
    }
    for (j = 1; j <= tot && i * pr[j] <= mx; ++j) {
      vis[i * pr[j]] = 1;
      if (i % pr[j] == 0) {
        miu[i * pr[j]] = 0;
        break;
      }
      miu[i * pr[j]] = -miu[i];
    }
    if (miu[i] != 0 && su[i] > 0 && ct[i] >= 2) {
      s = (s + miu[i] * 1ll * g(ct[i] - 2) % mod *
                   (1ll * su[i] * su[i] % mod - jian[i] + mod) % mod) %
          mod;
      s = (s + miu[i] * 1ll * h(ct[i] - 1) % mod * jian[i]) % mod;
    }
  }
  s = (s + mod) % mod;
  printf("%d\n", s);
  return 0;
}