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 long long h = 3, ki = 149, mo = 998244353;
long long mod(long long x) { return (x % mo + mo) % mo; }
long long inc(long long x, long long k) {
  x += k;
  return x < mo ? x : x - mo;
}
long long dec(long long x, long long k) {
  x -= k;
  return x >= 0 ? x : x + mo;
}
long long ksm(long long x, long long k) {
  long long ans = 1;
  while (k) {
    if (k & 1) ans = 1ll * ans * x % mo;
    k >>= 1;
    x = 1ll * x * x % mo;
  }
  return ans;
}
long long inv(long long x) { return ksm(mod(x), mo - 2); }
long long read() {
  char ch = 0;
  long long x = 0, flag = 1;
  while (!isdigit(ch)) {
    ch = getchar();
    if (ch == '-') flag = -1;
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  }
  return x * flag;
}
void write(long long x) {
  if (!x) return (void)putchar(48);
  if (x < 0) putchar(45), x = -x;
  long long len = 0, p[20];
  while (x) p[++len] = x % 10, x /= 10;
  for (long long i = len; i >= 1; i--) putchar(p[i] + 48);
}
const double eps = 1e-7, inf = 1e9 + 7, pi = acos(-1);
double Read() {
  double x;
  scanf("%lf", &x);
  return x;
}
void Write(double x) { printf("%lf", x); }
bool is_prime[1100000];
long long cnt, mu[1100000], mi[1100000], prime[1100000];
void prepare(long long n) {
  memset(is_prime, true, sizeof(is_prime));
  mu[1] = 1;
  is_prime[1] = false;
  for (long long i = 1; i <= n; i++) {
    if (is_prime[i]) mu[i] = -1, prime[++cnt] = i;
    for (long long j = 1; j <= cnt; j++) {
      long long x = i * prime[j];
      if (x > n) break;
      is_prime[x] = false;
      if (i % prime[j])
        mu[x] = -mu[i];
      else {
        mu[x] = 0;
        break;
      }
    }
  }
  mi[0] = 1;
  for (long long i = 1; i <= n; i++) mi[i] = 2ll * mi[i - 1] % mo;
}
long long sz[1100000], S1[1100000], S2[1100000];
int main() {
  long long n = read(), m = 2e5, res = 0, p = mo - 1;
  for (long long i = 1; i <= n; i++) {
    long long x = read(), t = read();
    sz[x] = t;
    S1[x] = 1ll * t * x % mo;
    S2[x] = 1ll * t * x % mo * x % mo;
  }
  prepare(m);
  int tot = 0;
  for (long long x = 1; x <= m; x++)
    if (mu[x]) {
      tot++;
      long long s1 = 0, s2 = 0, len = 0;
      for (long long i = x; i <= m; i += x)
        s1 = inc(s1, S1[i]), s2 = inc(s2, S2[i]), len += sz[i];
      long long ans =
          inc(1ll * mod(len) * ksm(2, (len - 3 + p) % p) % mo *
                  dec(1ll * s1 * s1 % mo, s2) % mo,
              1ll * mod(len - 1) * ksm(2, (len - 2 + p) % p) % mo * s2 % mo);
      res = inc(res, mod(mu[x] * ans));
    }
  write(mod(res));
  return 0;
}