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;
struct IO {
  IO() {
    ios::sync_with_stdio(0);
    cin.tie(0);
  }
} io;
using ll = long long;
using db = long double;
using pi = pair<ll, ll>;
using mi = map<ll, ll>;
const ll mod = 998244353;
const ll INF = 0x3f3f3f3f;
ll qpow(ll a, ll b, ll MOD = mod) {
  for (ll ans = 1;; a = a * a % MOD, b >>= 1) {
    if (b & 1) ans = ans * a % MOD;
    if (b <= 0) return ans;
  }
}
ll inv(ll a, ll MOD = mod) { return qpow(a, MOD - 2, MOD); }
ll exgcd(ll a, ll b, ll &x, ll &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  ll ret = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return ret;
}
ll getInv(ll a, ll mod) {
  ll x, y;
  ll d = exgcd(a, mod, x, y);
  return d == 1 ? (x % mod + mod) % mod : -1;
}
using vi = vector<ll>;
const ll N = 1e5 + 5, M = 998244353;
inline ll add(ll x, ll y) { return x + y >= M ? x + y - M : x + y; }
inline ll mul(ll x, ll y) { return x * y % M; }
inline ll sub(ll x, ll y) { return x - y < 0 ? x - y + M : x - y; }
using G = vector<vi>;
ll pri[N], vis[N], mu[N], tot;
void init() {
  mu[1] = 1;
  for (ll i = 2; i < N; i++) {
    if (!vis[i]) pri[++tot] = i, mu[i] = -1;
    for (ll j = 1; j <= tot && pri[j] * i < N; j++) {
      vis[pri[j] * i] = 1;
      if (i % pri[j] == 0) {
        mu[i * pri[j]] = 0;
        break;
      } else
        mu[i * pri[j]] = -mu[i];
    }
  }
}
ll a[N], num[N], fre[N];
signed main() {
  init();
  ll m;
  cin >> m;
  for (ll i = 1; i <= m; i++) cin >> a[i] >> fre[i], num[a[i]] = fre[i];
  ll ans = 0;
  for (ll i = 1; i < N; i++) {
    if (mu[i] == 0) continue;
    ll cnt = 0;
    ll s1 = 0, s2 = 0;
    for (ll j = i; j < N; j += i) {
      cnt += num[j];
      s1 = (s1 + j * num[j]) % mod;
      s2 = (s2 + j * j % mod * num[j]) % mod;
    }
    if (cnt < 2) continue;
    s1 = add(mul(s1, s1), -s2);
    s2 = mul(s2, mul((cnt - 1) % M, qpow(2, cnt - 2)));
    s1 = mul(s1, add(mul(qpow(2, cnt - 3), (cnt - 2) % M), qpow(2, cnt - 2)));
    ans = add(ans, mu[i] * add(s1, s2));
    ans = add(ans % mod, M);
  }
  cout << ans << endl;
}