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;
long long m, a, b, freq[100005], mob[100005], mod = 998244353ll, ans;
long long fastp(long long base, long long exp) {
  if (exp == 0) return 1;
  long long tmp = fastp(base, exp / 2);
  tmp = (tmp * tmp) % mod;
  if (exp % 2 == 1) tmp *= base;
  return tmp % mod;
}
long long f(long long x) {
  long long sum = 0, sum2 = 0, n = 0, esp = 0, coeff, coeff2;
  for (long long i = x; i <= 100000; i += x) {
    sum += (freq[i] * i) % mod;
    sum2 += (freq[i] * ((i * i) % mod)) % mod;
    n += freq[i];
    esp += freq[i];
    sum %= mod;
    sum2 %= mod;
    n %= mod;
    esp %= (mod - 1);
  }
  if (n == 2)
    coeff = 1;
  else
    coeff =
        (fastp(2, ((esp - 3) % (mod - 1) + (mod - 1)) % (mod - 1)) * n) % mod;
  coeff2 =
      (fastp(2, ((esp - 2) % (mod - 1) + (mod - 1)) % (mod - 1)) * (n - 1)) %
      mod;
  sum = (sum * sum) % mod;
  return ((sum - sum2) * coeff + sum2 * coeff2) % mod;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  mob[1] = 1;
  for (long long i = 2; i <= 100000; i++) {
    int num = -1;
    for (long long j = 2; j * j <= i; j++) {
      if (i % j == 0) {
        num = j;
        break;
      }
    }
    if (num == -1)
      mob[i] = -1;
    else {
      if ((i / num) % num == 0)
        mob[i] = 0;
      else
        mob[i] = mob[num] * mob[i / num];
    }
  }
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    freq[a] = b;
  }
  for (int i = 1; i <= 100000; i++) {
    ans += (f(i) * mob[i]) % mod;
    ans %= mod;
  }
  cout << (ans % mod + mod) % mod << "\n";
  return 0;
}