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 PYTHON3):

Solution:
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)