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 MAX_N = 100000;
const int MOD = 998244353;
long long fr[1 + MAX_N];
int primecnt[1 + MAX_N];
bool squared[1 + MAX_N];
int lgput(int b, long long e) {
  int ac = 1;
  while (e > 0) {
    if (e % 2 == 1) ac = (long long)ac * b % MOD;
    b = (long long)b * b % MOD;
    e /= 2;
  }
  return ac;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int v, f;
    scanf("%d%d", &v, &f);
    fr[v] = (fr[v] + f);
  }
  for (int d = 2; d <= MAX_N; ++d)
    if (primecnt[d] == 0)
      for (int i = d; i <= MAX_N; i += d) {
        if (i / d % d == 0) squared[i] = true;
        primecnt[i]++;
      }
  int res = 0;
  for (int d = 1; d <= MAX_N; ++d)
    if (!squared[d]) {
      int sum = 0, sumsqr = 0;
      long long freq = 0;
      for (int i = d; i <= MAX_N; i += d) {
        sum = ((long long)fr[i] % MOD * i + sum) % MOD;
        sumsqr = ((long long)fr[i] % MOD * i % MOD * i + sumsqr) % MOD;
        freq += fr[i];
      }
      int sum_pairs = ((long long)sum * sum + MOD - sumsqr) % MOD;
      if (freq >= 2) {
        int coef_sqr = (long long)lgput(2, freq - 2) * ((freq - 1) % MOD) % MOD;
        int coef_pairs = 0;
        coef_pairs = lgput(2, freq - 2);
        coef_pairs =
            ((long long)lgput(2, freq - 3) * ((freq - 2) % MOD) + coef_pairs) %
            MOD;
        int to_add =
            ((long long)coef_sqr * sumsqr + (long long)coef_pairs * sum_pairs) %
            MOD;
        if (primecnt[d] % 2 == 0)
          res = (res + to_add) % MOD;
        else
          res = (res + MOD - to_add) % MOD;
      }
    }
  printf("%d", res);
  return 0;
}