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>
const int M = 100000;
const int A = 100000;
const long long FREQ = 1000000000ll;
const long long mod = 998244353ll;
int m;
int a[M + 10];
long long freq[M + 10];
long long mu[A + 10];
bool notprime[A + 10];
int prime[A + 10];
inline long long up(long long x) { return x < 0 ? (x + mod) : x; }
inline long long down(long long x) { return x >= mod ? (x - mod) : x; }
inline void tup(long long& x) {
  (x < 0) && (x += mod);
  return;
}
inline void tdown(long long& x) {
  (x >= mod) && (x -= mod);
  return;
}
long long qpow(long long bas, long long ind) {
  if (ind < 0) ind += mod - 1;
  long long ans = 1ll;
  while (ind) {
    if (ind & 1) (ans *= bas) %= mod;
    (bas *= bas) %= mod;
    ind >>= 1;
  }
  return ans;
}
void euler_sieve() {
  prime[0] = 0;
  notprime[1] = true;
  mu[1] = 1ll;
  for (int i = 2; i <= A; ++i) {
    if (!notprime[i]) {
      prime[++prime[0]] = i;
      mu[i] = -1;
    }
    int nxt = 0;
    for (int j = 1; j <= prime[0] && (nxt = prime[j] * i) <= A; ++j) {
      notprime[nxt] = true;
      if (i % prime[j]) {
        mu[nxt] = -mu[i];
      } else {
        mu[nxt] = 0;
        break;
      }
    }
  }
  for (int i = 1; i <= A; ++i)
    if (mu[i] < 0) mu[i] += mod;
  return;
}
std::vector<int> v[A + 10];
void deco(int x, int id) {
  for (int i = 1; i * i <= x; ++i) {
    if (x % i == 0) {
      v[i].push_back(id);
      if (i * i != x) {
        v[x / i].push_back(id);
      }
    }
  }
  return;
}
long long sum = 0;
long long calc(int ind) {
  long long sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
  long long sumf = 0;
  for (int i = 0; i < v[ind].size(); ++i) {
    long long j = v[ind][i];
    long long ta = a[j], tf = freq[j];
    sumf += tf;
    (sum1 += ta * ta % mod * tf) %= mod;
    (sum2 += ta * ta % mod * tf % mod * (tf - 1)) %= mod;
    (sum3 += ta * tf) %= mod;
    (sum4 += ta * tf % mod * ta % mod * tf) %= mod;
  }
  (sum3 *= sum3) %= mod;
  long long sumfm = sumf % mod;
  long long summ =
      (qpow(2, sumf - 2) * (sumfm - 1 + mod) % mod * sum1 % mod +
       qpow(2, sumf - 3) * sumfm % mod * sum2 % mod +
       qpow(2, sumf - 3) * sumfm % mod * (sum3 - sum4 + mod) % mod) %
      mod;
  return summ;
}
int main() {
  euler_sieve();
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d %lld", &a[i], &freq[i]);
    deco(a[i], i);
  }
  for (int i = 1; i <= A; ++i) {
    if (mu[i]) {
      (sum += mu[i] * calc(i)) %= mod;
    }
  }
  printf("%lld\n", sum);
  return 0;
}