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 int MAX = 1e5;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 998244353;
template <typename T>
T mul(T a, T b) {
  return ((1LL * a * b) % MOD + MOD) % MOD;
}
template <typename T>
T add(T a, T b) {
  return ((a + b) % MOD + MOD) % MOD;
}
template <typename T, typename... V>
T mul(T t, V... v) {
  return mul(t, mul(v...));
}
template <typename T, typename... V>
T add(T t, V... v) {
  return add(t, add(v...));
}
long long pwr(long long a, long long b) {
  if (b == 0)
    return 1;
  else if (b == 2)
    return mul(a, a);
  else if (b & 1LL)
    return mul(a, pwr(a, b - 1));
  else
    return pwr(pwr(a, b / 2), 2);
}
long long i2, p2n1, p2n2;
long long A[100003];
long long count(int x) {
  vector<int> fac;
  int tmp = x;
  for (int i = 2; i <= sqrt(x); i++) {
    if (tmp % i == 0) {
      if (tmp % (i * i) == 0) return 0;
      tmp /= i;
      fac.push_back(i);
    }
  }
  if (tmp > 1) fac.push_back(tmp);
  long long sum = 0, num = 0;
  for (long long i = x; i <= MAX; i += x) {
    sum = add(sum, mul(i, A[i]));
    num = num + A[i];
  }
  if (num <= 1) return 0;
  long long res = 0;
  long long p2n1 = pwr(2, num - 1), p2n2 = pwr(2, num - 2);
  for (long long i = x; i <= MAX; i += x) {
    if (A[i] == 0) continue;
    res = add(res, mul(A[i], i, i, p2n1, (num - 1) % MOD, i2));
    res = add(res, mul(A[i], i, sum - i, p2n2, (num) % MOD, i2));
  }
  if (fac.size() & 1)
    return -res;
  else
    return res;
}
int main() {
  i2 = pwr(2, MOD - 2);
  int m;
  scanf("%d", &m);
  while (m--) {
    int x;
    scanf("%d", &x);
    scanf("%d", &A[x]);
  }
  long long res = 0;
  for (int i = 1; i <= MAX; i++) {
    res = add(res, count(i));
  }
  printf("%lld\n", res);
}