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 N = 1e5 + 7;
const int MAXN = 1e5;
const int mod = 998244353;
const int inv2 = (mod + 1) / 2;
int n, m, jc[N], njc[N];
int qpow(int x, long long y) {
  int res = 1;
  for (; y; x = 1ll * x * x % mod, y >>= 1)
    if (y & 1) res = 1ll * res * x % mod;
  return res;
}
int ny(int x) { return qpow(x, mod - 2); }
int C(int x, int y) { return 1ll * jc[x] * njc[y] % mod * njc[x - y] % mod; }
int cnt[N], ans[N];
long long SZ[N];
void work(int x) {
  long long siz = 0;
  int sumf = 0, sum = 0;
  for (int i = 1, iE = MAXN / x; i <= iE; i++)
    siz += SZ[i * x], (sum += 1ll * cnt[i * x] * (i * x) % mod) %= mod,
        (sumf += 1ll * cnt[i * x] * (i * x) % mod * (i * x) % mod) %= mod;
  int suma = 0, sumb = 0;
  if (siz > 1) suma = 1ll * siz % mod * qpow(2, siz - 2) % mod * inv2 % mod;
  (ans[x] += (1ll * sum * sum - sumf + mod) % mod * suma % mod) %= mod;
  if (siz) sumb = 1ll * (siz - 1) % mod * qpow(2, siz - 1) % mod * inv2 % mod;
  (ans[x] += 1ll * sumf * sumb % mod) %= mod;
  for (int i = 2, iE = MAXN / x; i <= iE; i++)
    (ans[x] += mod - ans[x * i]) %= mod;
}
int main() {
  scanf("%d", &n);
  jc[0] = njc[0] = 1;
  for (int i = 1, iE = MAXN; i <= iE; i++)
    jc[i] = 1ll * jc[i - 1] * i % mod, njc[i] = ny(jc[i]);
  for (int i = 1, iE = n; i <= iE; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    (cnt[x] += y) %= mod, SZ[x] += y;
  }
  for (int i = MAXN, iE = 1; i >= iE; i--) work(i);
  printf("%d\n", ans[1]);
  return 0;
}