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;
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf("%c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
const long long mod = 998244353;
const int MAXN = 100000;
bool isNotPrime[MAXN + 1];
int mu[MAXN + 1], prime[MAXN + 1], nt;
inline void euler() {
  isNotPrime[0] = isNotPrime[1] = true;
  mu[1] = 1;
  for (int i = 2; i <= MAXN; i++) {
    if (!isNotPrime[i]) {
      prime[++nt] = i;
      mu[i] = mod - 1;
    }
    for (int j = 1; j <= nt && i * prime[j] <= MAXN; j++) {
      isNotPrime[i * prime[j]] = true;
      if (i % prime[j] == 0)
        mu[i * prime[j]] = 0;
      else
        mu[i * prime[j]] = mod - mu[i];
    }
  }
}
long long qpow(long long a, long long b) {
  b %= (mod - 1);
  long long r = 1;
  while (b) {
    if (b & 1) r = r * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return r;
}
long long sum[100005];
long long sum2[100005];
long long cnt[100005];
long long ans[100005];
int m;
int main() {
  euler();
  R(m);
  for (int i = 1, a, f; i <= m; ++i) {
    R(a, f);
    for (int j = 1; j * j <= a; ++j) {
      if (a % j) continue;
      sum[j] = (sum[j] + 1ll * a * f % mod) % mod;
      sum2[j] = (sum2[j] + 1ll * a * a % mod * f % mod) % mod;
      cnt[j] += f;
      if (j * j != a) {
        sum[a / j] = (sum[a / j] + 1ll * a * f) % mod;
        sum2[a / j] = (sum2[a / j] + 1ll * a * a % mod * f) % mod;
        cnt[a / j] += f;
      }
    }
  }
  for (int i = 1; i <= 100000; ++i) {
    if (cnt[i] <= 1) continue;
    ans[i] = (ans[i] + sum2[i] * qpow(2ll, cnt[i] - 2) % mod *
                           ((cnt[i] - 1) % mod) % mod) %
             mod;
    if (cnt[i] == 2)
      ans[i] = (ans[i] + sum[i] * sum[i] % mod - sum2[i] + mod) % mod;
    if (cnt[i] <= 2) continue;
    ans[i] = (ans[i] + (sum[i] * sum[i] % mod - sum2[i] + mod) % mod *
                           qpow(2ll, cnt[i] - 3) % mod * (cnt[i] % mod) % mod) %
             mod;
  }
  long long res = 0;
  for (int i = 1; i <= 100000; ++i)
    res = (res + 1ll * mu[i] * ans[i] % mod) % mod;
  W(res);
  return 0;
}
