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.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, size = 1 << 20, mod = 998244353, inf = 2e9;
const long long INF = 1e15;
template <class o>
void qr(o& x) {
  char c = getchar();
  x = 0;
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  x *= f;
}
template <class o>
void qw(o x) {
  if (x / 10) qw(x / 10);
  putchar(x % 10 + '0');
}
template <class o>
void pr1(o x) {
  if (x < 0) x = -x, putchar('-');
  qw(x);
  putchar(' ');
}
template <class o>
void pr2(o x) {
  if (x < 0) x = -x, putchar('-');
  qw(x);
  putchar('\n');
}
long long gcd(long long a, long long b) { return !a ? b : gcd(b % a, a); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long power(long long a, long long b = mod - 2, long long p = mod) {
  long long c = 1;
  while (b) {
    if (b & 1) c = c * a % p;
    b /= 2;
    a = a * a % p;
  }
  return c;
}
template <class o>
void cmax(o& x, o y) {
  if (x < y) x = y;
}
void cmax(int& x, int y) {
  x = x - y >> 31 ? y : x;
  ;
}
template <class o>
void cmin(o& x, o y) {
  if (x > y) x = y;
}
void cmin(int& x, int y) { x = x - y >> 31 ? x : y; }
template <typename t1, typename t2>
void ad(t1& x, t2 y) {
  x += y;
  if (x >= mod) x -= mod;
}
template <typename t1, typename t2>
void dl(t1& x, t2 y) {
  x -= y;
  if (x < 0) x += mod;
}
int n;
const int M = 1 << 15;
long long p1[M | 5], p2[M | 5];
long long p(long long b) {
  b %= mod - 1;
  if (b < 0) b += mod - 1;
  return p1[b & (M - 1)] * p2[b >> 15] % mod;
}
long long cnt[N], s[N], same[N], dif[N], f[N];
void solve() {
  n = M;
  p1[0] = 1;
  for (int i = 1; i <= n; i++) p1[i] = p1[i - 1] * 2 % mod;
  p2[0] = 1;
  p2[1] = p1[n];
  for (int i = 2; i <= n; i++) p2[i] = p2[i - 1] * p2[1] % mod;
  qr(n);
  int mx = 0, x;
  long long c;
  for (int i = 1; i <= n; i++) {
    qr(x);
    qr(c);
    cnt[x] = c;
    s[x] = x * c % mod;
    same[x] = s[x] * x % mod;
    dif[x] = c * (c - 1) / 2 % mod * x % mod * x % mod;
    cmax(mx, x);
  }
  for (int i = 1; i <= mx; i++) {
    for (int j = 2 * i; j <= mx; j += i) {
      cnt[i] += cnt[j];
      ad(dif[i], (s[i] * s[j] + dif[j]) % mod);
      ad(same[i], same[j]);
      ad(s[i], s[j]);
    }
  }
  for (int i = mx; i >= 1; i--) {
    long long k = cnt[i];
    f[i] = same[i] * p(k - 2) % mod * ((k - 1) % mod) +
           dif[i] * (p(k - 2) * (k % mod) % mod);
    f[i] = (f[i] % mod + mod) % mod;
    for (int j = 2 * i; j <= mx; j += i) dl(f[i], f[j]);
  }
  pr2(f[1]);
}
int main() {
  int T = 1;
  while (T--) solve();
  return 0;
}
