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;
inline long long rd() {
  long long x = 0;
  char c = getchar();
  bool f = 0;
  while (c < '0' && c != '-') c = getchar();
  if (c == '-') f = 1, c = getchar();
  while (c >= '0') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return f ? -x : x;
}
const long long SIZE = 1e5 + 100;
const long long Mod = 998244353;
long long m;
long long a[SIZE], fre[SIZE], ans[SIZE];
vector<long long> P[SIZE], V[SIZE];
long long Pow(long long a, long long b) {
  if (b < 0) return 0;
  long long res = 1;
  while (b) {
    if (b & 1) res = 1LL * res * a % Mod;
    b >>= 1;
    a = 1LL * a * a % Mod;
  }
  return res;
}
void _main() {
  long long mx = 0;
  for (long long i = 1; i <= 100000; ++i) {
    for (long long j = i; j <= 100000; j += i) P[j].push_back(i);
    mx = max(mx, (long long)P[i].size());
  }
  m = rd();
  for (register long long i = 1, _n = m; i <= _n; ++i) {
    a[i] = rd(), fre[i] = rd();
    for (long long v : P[a[i]]) V[v].push_back(i);
  }
  for (register long long G = 100000, _n = 1; G >= _n; --G) {
    long long n = 0;
    long long sum = 0;
    for (long long i : V[G])
      n += fre[i], sum = (sum + 1LL * fre[i] * a[i]) % Mod;
    long long pw3 = Pow(2, n - 3), pw2 = Pow(2, n - 2), pw1 = Pow(2, n - 1);
    for (long long i : V[G]) {
      ans[G] = (ans[G] +
                1LL * a[i] * fre[i] % Mod * (sum + Mod - a[i]) % Mod * pw2) %
               Mod;
      ans[G] = (ans[G] + 1LL * a[i] * a[i] % Mod * fre[i] % Mod * pw1) % Mod;
    }
    if (ans[G]) ans[G] = Mod - ans[G];
    for (long long i : V[G]) {
      ans[G] = (ans[G] + 1LL * a[i] * fre[i] % Mod * (sum + Mod - a[i]) % Mod *
                             (pw1 + (n - 2) % Mod * pw3 % Mod)) %
               Mod;
      ans[G] = (ans[G] + 1LL * a[i] * a[i] % Mod * fre[i] % Mod *
                             (pw1 + (n - 1) % Mod * pw2 % Mod)) %
               Mod;
    }
    for (long long j = G + G; j <= 100000; j += G)
      ans[G] = (ans[G] + Mod - ans[j]) % Mod;
  }
  cout << ans[1] << endl;
}
signed main() {
  _main();
  return 0;
}