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>
#pragma GCC optimize("O3")
using namespace std;
const int maxn = 1e5 + 3;
const int mod = 998244353;
int n;
pair<int, int> c[maxn];
void read() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> c[i].first >> c[i].second;
}
int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
  return a;
}
int fast_pow(int x, long long deg) {
  int ans = 1, y = x;
  while (deg) {
    if (deg & 1) ans = 1ll * ans * y % mod;
    deg /= 2;
    y = 1ll * y * y % mod;
  }
  return ans;
}
int f(vector<int> v) {
  long long m = 0;
  for (auto i : v) m += c[i].second;
  if (m <= 1) return 0;
  int ans = 0;
  if (m >= 2) {
    int sum = 0;
    for (auto i : v)
      sum = add(sum, 1ll * c[i].first * c[i].first % mod * c[i].second % mod);
    ans =
        add(ans, 1ll * sum * ((m - 1) % mod) % mod * fast_pow(2, m - 2) % mod);
  }
  int sum = 0;
  for (auto i : v) sum = add(sum, 1ll * c[i].first * c[i].second % mod);
  int mult = fast_pow(2, m - 2);
  if (m >= 3)
    mult = add(mult, 1ll * fast_pow(2, m - 3) * ((m - 2) % mod) % mod);
  for (auto i : v)
    ans = add(ans, 1ll * c[i].second * c[i].first % mod *
                       add(sum, -c[i].first) % mod * mult % mod);
  return ans;
}
int ans[maxn];
int idx[maxn];
void solve() {
  for (int i = 1; i <= n; i++) idx[c[i].first] = i;
  for (int i = maxn - 1; i >= 1; i--) {
    vector<int> v;
    for (int j = i; j < maxn; j += i)
      if (idx[j] != 0) v.push_back(idx[j]);
    ans[i] = f(v);
    for (int j = i * 2; j < maxn; j += i) ans[i] = add(ans[i], -ans[j]);
  }
  cout << ans[1] << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  read();
  solve();
}