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;
const long long iinf = 1e9 + 10;
const long long inf = 1ll << 60;
const long long MOD = 998244353;
void GG() {
  cout << "0\n";
  exit(0);
}
const long long maxn = 1e5 + 5;
vector<pair<long long, long long> > here[maxn];
template <long long mod>
struct Modint {
  long long val;
  Modint(long long _val = 0) { val = _val; }
  operator long long() const { return (*this).val; }
  Modint operator+(const Modint& o) const {
    return val + o.val >= mod ? Modint(val + o.val - mod) : Modint(val + o.val);
  }
  Modint operator-() const { return val ? Modint(mod - val) : *this; }
  Modint operator-(const Modint& o) const {
    return val - o.val < 0 ? Modint(val - o.val + mod) : Modint(val - o.val);
  }
  Modint operator*(const Modint& o) const { return Modint(val * o.val % mod); }
  Modint operator+=(const Modint& o) {
    *this = (*this) + o;
    return *this;
  }
  Modint operator-=(const Modint& o) {
    *this = (*this) - o;
    return *this;
  }
  Modint operator*=(const Modint& o) {
    *this = (*this) * o;
    return *this;
  }
  Modint Pow(long long b) const {
    Modint tmp(val), ret(1);
    while (b) {
      if (b & 1) ret *= tmp;
      b >>= 1;
      tmp *= tmp;
    }
    return ret;
  }
  Modint Pow(const Modint& a, long long b) const { return a.Pow(b); }
  inline Modint inv() const { return (*this).Pow(mod - 2); }
  Modint operator/(const Modint& o) const { return *this * o.inv(); }
  bool operator==(const Modint& o) const { return val == o.val; }
};
Modint<MOD> mpow(Modint<MOD> a, long long n, long long mo = MOD) {
  Modint<MOD> re = 1;
  while (n > 0) {
    if (n & 1) re = re * a % mo;
    a = a * a % mo;
    n >>= 1;
  }
  return re;
}
Modint<MOD> inv(long long b, long long mo = MOD) {
  if (b == 1) return b;
  return (mo - mo / b) * inv(mo % b, mo) % mo;
}
const Modint<MOD> i4 = inv(4);
const Modint<MOD> i2 = inv(2);
Modint<MOD> go(long long x) {
  ;
  Modint<MOD> oth2 = 0;
  Modint<MOD> oth1 = 0;
  Modint<MOD> oth0 = 1;
  Modint<MOD> siga = 0;
  long long sigf = 0;
  for (pair<long long, long long>& p : here[x]) {
    Modint<MOD> a = p.first, first = p.second;
    Modint<MOD> mf = mpow(2, first);
    oth2 = mf * oth2 +
           oth0 * a * a * mf * i4 * first * (first + (Modint<MOD>)1) +
           oth1 * (Modint<MOD>)2 * a * mf * i2 * first;
    siga += a * first;
    sigf += first;
    sigf %= (MOD - 1);
    Modint<MOD> m2 = mpow(2, sigf);
    oth1 = siga * m2 * i2;
    oth0 = m2;
  }
  Modint<MOD> mpowsigf = mpow(2, sigf);
  ;
  Modint<MOD> re = 0;
  for (pair<long long, long long>& p : here[x]) {
    Modint<MOD> a = p.first, first = p.second;
    Modint<MOD> have1 = siga * mpowsigf * i4 + a * mpowsigf * inv(4);
    Modint<MOD> two = a * a * mpowsigf * i2 + oth2 + oth1 * (Modint<MOD>)2 * a -
                      (Modint<MOD>)2 * a * have1;
    two *= i2;
    ;
    re += two * first;
  };
  return re - oth2;
}
long long mob[maxn];
bool np[maxn];
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  long long n;
  cin >> n;
  for (long long i = 0; i < n; ++i) {
    long long a, first;
    cin >> a >> first;
    for (long long j = 1; j <= sqrt(a); ++j) {
      if (a % j == 0) {
        here[j].push_back({a, first});
        if (j * j != a) {
          here[a / j].push_back({a, first});
        }
      }
    }
  }
  fill(mob, mob + maxn - 1, 1);
  for (long long i = 2; i < maxn; ++i) {
    if (!np[i]) {
      mob[i] = -1;
      for (long long j = i + i; j < maxn; j += i) {
        mob[j] = -mob[j];
        np[j] = 1;
      }
      if (i * i <= maxn)
        for (long long j = i * i; j < maxn; j += i * i) {
          mob[j] = 0;
        }
    }
  }
  long long re = 0;
  for (long long i = 0; i < maxn; ++i) {
    if (mob[i] && (long long)here[i].size()) {
      re += mob[i] * go(i);
      re %= MOD;
    }
  }
  cout << (re + MOD) % MOD << '\n';
}