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;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rnd64(
    chrono::high_resolution_clock::now().time_since_epoch().count());
long long power(long long a, long long m, long long mod) {
  long long ans = 1;
  while (m) {
    if (m % 2) ans *= a, ans %= (mod);
    a = (a * a) % mod;
    m >>= 1;
  }
  return ans;
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  size_t operator()(pair<int64_t, int64_t> Y) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(Y.first * 31 + Y.second + FIXED_RANDOM);
  }
};
const long long inf = 1e18;
const long long M = 998244353;
long long func(vector<pair<long long, long long> > &v) {
  long long tot = 0;
  for (auto &i : v) tot += i.second, tot;
  if (tot < 2) return 0;
  if (tot == 2) {
    vector<long long> v1;
    tot = 0;
    for (auto &i : v) {
      for (int j = 0; j < i.second; ++j) tot += i.first, tot;
    }
    return tot * tot % M;
  }
  long long ans = 0;
  long long n = v.size(), i;
  long long p1 = power(2, M - 2, M);
  long long p2 = power(2, tot - 2, M);
  long long p3 = power(2, tot - 3, M);
  tot %= M;
  for (i = 0; i < n; i++)
    ans +=
        p2 * v[i].first % M * v[i].first % M * (tot - 1) % M * v[i].second % M,
        ans %= M;
  long long sum = 0;
  for (auto &i : v) sum += i.first * i.second % M, sum %= M;
  for (auto &i : v) {
    sum -= i.first * i.second % M, sum += M, sum %= M;
    if (i.second >= 2)
      ans += i.second * (i.second - 1) % M * p1 % M *
             ((p2 + p3 * (tot - 2) % M) % M) % M * i.first % M * i.first % M *
             2 % M;
    ans %= M;
    ans += 2 * i.first % M * sum % M * ((p2 + p3 * (tot - 2) % M) % M) % M *
           i.second % M;
    ans %= M;
  }
  return ans;
}
void solve() {
  long long i, j, _;
  long long n;
  cin >> n;
  vector<pair<long long, long long> > a(n);
  for (i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
  long long ans[100001] = {0};
  vector<pair<long long, long long> > v[100001];
  for (auto &i : a) {
    for (j = 1; j * j <= i.first; ++j) {
      if (i.first % j) continue;
      v[j].push_back(i);
      if (i.first / j != j) v[i.first / j].push_back(i);
    }
  }
  for (i = 100000; i > 0; i--) {
    ans[i] = func(v[i]);
    for (j = 2 * i; j < 100001; j += i)
      ans[i] -= ans[j], ans[i] += M, ans[i] %= M;
  }
  cout << ans[1] << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long T = 1;
  while (T--) {
    solve();
  }
  return 0;
}
