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;
mt19937 rnd(51);
const int N = 1e5 + 10, MOD = 998244353;
int col[N], take[N], sum[N], ans[N];
long long cnt[N];
vector<int> b[N];
int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
int sub(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  return a;
}
int mul(int a, int b) { return ((long long)a * b % MOD); }
int binpow(int a, long long n) {
  if (n == 0) return 1;
  if (n & 1) {
    return mul(binpow(a, n - 1), a);
  } else {
    int g = binpow(a, n / 2);
    return mul(g, g);
  }
}
int val(long long n) {
  if (n == 1) return 0;
  if (n == 2) return 1;
  return mul(n % MOD, binpow(2, n - 3));
}
int vall(long long n) {
  if (n == 1) return 0;
  return mul((n - 1) % MOD, binpow(2, n - 2));
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    cin >> col[a[i]];
    take[a[i]] = mul(a[i], col[a[i]]);
    b[a[i]].emplace_back(a[i]);
    cnt[a[i]] += col[a[i]];
    sum[a[i]] = add(sum[a[i]], take[a[i]]);
  }
  for (int i = N - 1; i >= 1; --i) {
    long long cntt = 0, summ = 0;
    for (int j = i; j < N; j += i) {
      cntt += cnt[j];
      summ = add(summ, sum[j]);
    }
    if (cntt == 0) continue;
    int first_val = val(cntt), second_val = vall(cntt);
    for (int j = i; j < N; j += i) {
      for (auto t : b[j]) {
        ans[i] = add(ans[i], mul(summ, mul(first_val, take[t])));
      }
      for (auto t : b[j]) {
        ans[i] = add(ans[i],
                     mul(col[t], mul(sub(second_val, first_val), mul(t, t))));
      }
    }
    for (int j = i * 2; j < N; j += i) {
      ans[i] = sub(ans[i], ans[j]);
    }
  }
  cout << ans[1] << endl;
  return 0;
}