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;
void read(int &x) {
  static char c;
  int f = 0;
  while (!isdigit(c = getchar()))
    if (c ^ 45) f = 1;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
  if (f) x = -x;
}
void read(long long &x) {
  static char c;
  int f = 0;
  while (!isdigit(c = getchar()))
    if (c ^ 45) f = 1;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
}
void read(unsigned int &x) {
  static char c;
  while (!isdigit(c = getchar()))
    ;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
}
void read(unsigned long long &x) {
  static char c;
  while (!isdigit(c = getchar()))
    ;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
}
void chkmax(int &x, int y) {
  if (y > x) x = y;
}
void chkmin(int &x, int y) {
  if (y < x) x = y;
}
void chkmax(long long &x, long long y) {
  if (y > x) x = y;
}
void chkmin(long long &x, long long y) {
  if (y < x) x = y;
}
void chkmax(unsigned int &x, unsigned int y) {
  if (y > x) x = y;
}
void chkmin(unsigned int &x, unsigned int y) {
  if (y < x) x = y;
}
void chkmax(unsigned long long &x, unsigned long long y) {
  if (y > x) x = y;
}
void chkmin(unsigned long long &x, unsigned long long y) {
  if (y < x) x = y;
}
const int N = 1e5 + 10, U = 1e5, Mod = 998244353;
void Add(int &x, int y) { (x += y) >= Mod ? x -= Mod : x; }
int Pow(int a, int b) {
  int Ans = 1;
  while (b) {
    if (b & 1) Ans = 1ll * Ans * a % Mod;
    a = 1ll * a * a % Mod, b >>= 1;
  }
  return Ans;
}
int m;
int val, freq;
int Prm[N], vis[N], mu[N], cnt;
void Euler() {
  mu[1] = 1;
  for (int i = 2; i <= U; ++i) {
    if (!vis[i]) Prm[++cnt] = i, mu[i] = Mod - 1;
    for (int j = 1; j <= cnt && i * Prm[j] <= U; ++j) {
      vis[i * Prm[j]] = 1;
      if (i % Prm[j] == 0) break;
      mu[i * Prm[j]] = Mod - mu[i];
    }
  }
}
int C1[N], C2[N], S[N];
long long rS[N];
void Work() {
  Euler();
  read(m);
  auto Update = [](int d, int val, int freq) -> void {
    Add(C1[d], 1ll * val * freq % Mod),
        Add(C2[d], 1ll * val * val % Mod * freq % Mod), rS[d] += freq;
  };
  for (int i = 1; i <= m; ++i) {
    read(val), read(freq);
    for (int d = 1; d * d <= val; ++d) {
      if (val % d) continue;
      Update(d, val, freq);
      if (val != d * d) Update(val / d, val, freq);
    }
  }
  int Ans = 0;
  for (int i = 1; i <= U; ++i) {
    if (rS[i] < 2 || !mu[i]) continue;
    C1[i] = 1ll * C1[i] * C1[i] % Mod;
    int p = Pow(2, (rS[i] - 2) % (Mod - 1));
    if (rS[i] > 2)
      Add(p, (rS[i] - 2) % Mod * Pow(2, (rS[i] - 3) % (Mod - 1)) % Mod);
    int t = 1ll * (C1[i] + Mod - C2[i]) % Mod * p % Mod;
    p = 1ll * (rS[i] - 1) % Mod * Pow(2, (rS[i] - 2) % (Mod - 1)) % Mod;
    Add(t, 1ll * p * C2[i] % Mod);
    Add(Ans, 1ll * mu[i] * t % Mod);
  }
  printf("%d\n", Ans);
}
int main() { Work(); }