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>
const int MAXN = 200005;
const long long MOD = (long long)998244353;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long sum[MAXN], sqsum[MAXN], cnt[MAXN], mob[MAXN], mpf[MAXN];
long long qpow(long long a, long long pw) {
  long long res = 1;
  while (pw) {
    if (pw % 2) {
      res = res * a % MOD;
    }
    a = a * a % MOD;
    pw >>= 1;
  }
  return res;
}
long long sq(long long x) { return x * x % MOD; }
long long coe_diff(long long n) {
  if (n < 2) return 0;
  if (n == 2) return 1;
  return (qpow(2, n - 3) * (n % MOD - 2) + qpow(2, n - 2)) % MOD;
}
long long coe_same(long long n) {
  if (n <= 1) return 0;
  return qpow(2, n - 2) * (n % MOD - 1) % MOD;
}
void solve() {
  for (int i = 1; i < MAXN; i++) {
    mpf[i] = i;
  }
  mob[1] = 1;
  for (int i = 2; i < MAXN; i++) {
    if (mpf[i] == i) {
      for (int j = i + i; j < MAXN; j += i) {
        mpf[j] = i;
      }
    }
    mob[i] = ((i / mpf[i]) % mpf[i] == 0 ? 0 : -1 * mob[i / mpf[i]]);
  }
  long long n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    long long a;
    cin >> a;
    cin >> cnt[a];
  }
  for (int i = 0; i < MAXN; i++) {
    sum[i] = cnt[i] * i % MOD;
    sqsum[i] = sq(i) * cnt[i] % MOD;
  }
  for (int i = 1; i < MAXN; i++) {
    for (int j = i + i; j < MAXN; j += i) {
      sum[i] += sum[j];
      cnt[i] += cnt[j];
      sqsum[i] += sqsum[j];
      sum[i] %= MOD;
      sqsum[i] %= MOD;
    }
  }
  long long ans = 0;
  for (int i = 1; i < MAXN; i++) {
    if (mob[i] == 0) continue;
    long long same = sqsum[i], diff = (sq(sum[i]) - same + MOD) % MOD;
    long long res1 = mob[i] * same % MOD * coe_same(cnt[i]) % MOD;
    long long res2 = mob[i] * diff % MOD * coe_diff(cnt[i]) % MOD;
    ans = (ans + res1 + res2) % MOD;
  }
  ans = (ans % MOD + MOD) % MOD;
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int tc = 1;
  for (int i = 1; i <= tc; i++) {
    solve();
  }
  return 0;
}