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

Solution:
import java.io.*; import java.util.*;
public class CF1436F{
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        
    } 
    public static class Pair implements Comparable<Pair>{
        int vtx; int val;
        public Pair(int a, int b){
            this.vtx=a; this.val=b;
        }
        public int compareTo(Pair other){
            if(this.val<other.val)return -1;
            if(this.val>other.val)return 1;
            if(this.vtx<other.vtx)return -1;
            return 1;
        }
    }
    static long MOD=998244353;
    static int MAXN=100001;
    
    static long[] cnt=new long[MAXN];
    static long[] sum=new long[MAXN];
    static long[] sum2=new long[MAXN];
    public static void main(String[] args){
       //ArrayList<Integer> test=add(76614); System.out.println(test);
        
        FastReader br=new FastReader();
        int M=br.nextInt(); 
        
        int a; long f; long q;
        
        for (int i = 0; i < M; i++) {
            a=br.nextInt(); f=br.nextInt();
            //ArrayList<Integer> c=add(a);
            //System.out.println(c);
            for(int j=1; j*j<=a; j++){ 
                if(a%j>0){continue;}
                cnt[j]+=f; q=f; q*=a; q%=MOD;
                sum[j]+=q; sum[j]%=MOD; q*=a; q%=MOD;
                sum2[j]+=q; sum2[j]%=MOD;
                if(a/j==j){continue;}
                cnt[a/j]+=f; q=f; q*=a; q%=MOD;
                sum[a/j]+=q; sum[a/j]%=MOD; q*=a; q%=MOD;
                sum2[a/j]+=q; sum2[a/j]%=MOD;
            }
            
        }
        //System.out.println(cnt[1]+" "+sum[1]+" "+sum2[1]);
        long[] x=new long[MAXN]; long n;
        
        long cur;
        for (int i = MAXN-1; i >0; i--) {
            if(cnt[i]<2)continue; //ans[i] and ans[ki]=0
            
            n=cnt[i];//Can't be modded
            cur=mult(mult((n-1)%MOD,pow(n-2)),sum2[i]);x[i]+=cur;
            //System.out.println(sum2[i]);
            cur=(mult(sum[i],sum[i]))%MOD-sum2[i]; cur%=MOD;
            //System.out.println(cur);
            
            if(n>2) {cur=mult(pow(n-3),mult(cur,n%MOD)); }
            x[i]=add(x[i],cur);
            
            //System.out.println(i+" "+ans[i]);
            for (int j = 2*i; j < MAXN; j+=i) {
                x[i]=add(x[i],-x[j]);
            }
            //System.out.println(i+" "+ans[i]);
        }
        
        System.out.println((x[1]+MOD)%MOD);
    }
    /*
    public static ArrayList<Integer> add(int a){
        //System.out.println(a);
        ArrayList<Integer> cur=new ArrayList<>(); cur.add(1); int po=1;
        if(a==1)return cur;
        boolean f=true;
        for (int i = 2; i*i<=a; i++) {
            
            f=true;
            if(a%i>0)continue;
            cur.add(i); po=i; a/=i;f=false;
            
            while(a%i==0){
                po*=i; a/=i; cur.add(po); 
            }
 
            break;
        }
        //System.out.println(f);
        if(f && a>1){
            ArrayList<Integer> b=new ArrayList<>(); b.add(1); b.add(a);
            ArrayList<Integer> c=new ArrayList<>();
            for (int i = 0; i < b.size(); i++) {
                for (int j = 0; j < cur.size(); j++) {
                    c.add(b.get(i)*cur.get(j));
                }
            }
 
            return c;
        }
        //System.out.println(a);
        ArrayList<Integer> b=add(a);
        ArrayList<Integer> c=new ArrayList<>();
        for (int i = 0; i < b.size(); i++) {
            for (int j = 0; j < cur.size(); j++) {
                c.add(b.get(i)*cur.get(j));
            }
        }
        return c;
    }*/
    public static long add(long a, long b){
        return ((a+b)%MOD+MOD)%MOD;
    }
    public static long mult(long a, long b){
        long c=(a*b)%MOD; if(c<0)c+=MOD;
        return c;
    }
    public static long pow(long e){
        e%=(MOD-1);
        if(e==0)return 1; if(e==1)return 2;
        long x=pow(e/2);
        x*=x; x%=MOD;
        x*=pow(e%2); x%=MOD; return x;
    }
    
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!