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.

Difficulty: VERY_HARD
Tags: Number theory

Combinatorics

Mathematics

Starter code:

Solutions:
import sys
input = sys.stdin.readline
max_n = 10 ** 5 + 1
mod = 998244353
spf = [i for i in range(max_n)]
prime = [True for i in range(max_n)]
mobius = [0 for i in range(max_n)]
prime[0] = prime[1] = False
mobius[1] = 1
primes = []
for i in range(2, max_n):
	if prime[i]:
		spf[i] = i
		mobius[i] = -1
		primes.append(i)
	for j in primes:
		prod = j * i
		if j > spf[i] or prod >= max_n:
			break
		spf[prod] = j
		prime[prod] = False
		if spf[i] == j:
			mobius[prod] = 0
		else:
			mobius[prod] = -mobius[i]
m = int(input())
freq = [0 for i in range(max_n)]
ans = 0
for i in range(m):
	(a, f) = map(int, input().split())
	freq[a] = f
for i in range(1, max_n):
	if mobius[i] != 0:
		cnt = 0
		val = 0
		square_val = 0
		for j in range(i, max_n, i):
			cnt += freq[j]
			val = (val + j * freq[j]) % mod
			square_val = (square_val + j * j * freq[j]) % mod
		tmp = 0
		if cnt > 1:
			f1 = 1
			g1 = 1
			if cnt < 3:
				f1 = mod - 2
				g1 = -1
			f2 = 1
			g2 = 1
			if cnt < 2:
				f2 = mod - 2
				g2 = -1
			p1 = cnt * pow(2, g1 * (cnt - 3) * f1, mod) % mod
			p2 = (cnt - 1) * pow(2, g2 * (cnt - 2) * f2, mod) % mod
			tmp = (val * val * p1 % mod + square_val * (p2 - p1) % mod) % mod
		ans = (ans + mobius[i] * tmp) % mod
print(ans)


import sys
input = sys.stdin.readline
max_n = 10 ** 5 + 1
mod = 998244353
spf = [i for i in range(max_n)]
prime = [True for i in range(max_n)]
mobius = [0 for i in range(max_n)]
prime[0] = prime[1] = False
mobius[1] = 1
primes = []
for i in range(2, max_n):
	if prime[i]:
		spf[i] = i
		mobius[i] = -1
		primes.append(i)
	for j in primes:
		prod = j * i
		if j > spf[i] or prod >= max_n:
			break
		spf[prod] = j
		prime[prod] = False
		if spf[i] == j:
			mobius[prod] = 0
		else:
			mobius[prod] = -mobius[i]
m = int(input())
freq = [0 for i in range(max_n)]
ans = 0
for i in range(m):
	(a, f) = map(int, input().split())
	freq[a] = f
for i in range(1, max_n):
	if mobius[i] != 0:
		cnt = 0
		val = 0
		val_square = 0
		for j in range(i, max_n, i):
			cnt += freq[j]
			val = (val + j * freq[j]) % mod
			val_square = (val_square + j * j * freq[j]) % mod
		if cnt < 2:
			continue
		p = pow(2, cnt - 2, mod)
		n1 = (cnt - 1) * p % mod
		n2 = p
		if cnt >= 3:
			n2 = n2 + (cnt - 2) * pow(2, cnt - 3, mod)
		diff_val = (val * val - val_square) % mod
		ans = (ans + mobius[i] * (n1 * val_square + n2 * diff_val)) % mod
print(ans)