1436_F. Sum Over Subsets
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.
```python
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)
    

```