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.util.*;
import java.io.*;
public class EdF {
	static long[] mods = {1000000007, 998244353, 1000000009};
	static long mod = mods[1];
	public static MyScanner sc;
    public static PrintWriter out;
	public static void main(String[] omkar) throws Exception{
		// TODO Auto-generated method stub
 		sc = new MyScanner();
 		PrintWriter out = new PrintWriter(System.out);
 		int m = sc.nextInt();
 		Map<Long, Long> freq = new HashMap<Long, Long>();
 		for(int j = 0;j<m;j++){
 			long num = sc.nextInt();
 			long fr = sc.nextInt();
 			freq.put(num, fr);
 		}
 		int[] mobius = mobiusAndPrime(100001);
 		long[] totaa = new long[100001];
 		long[] sum0a = new long[100001];
 		long[] sumsqa = new long[100001];
 		for(long j = 1;j<=100000;j++){
 			for(long k =j;k<=100000;k+=j){
 				if (freq.keySet().contains(k)){
 					
 					totaa[(int)j]+=(long)(freq.get(k));
 					
 					sum0a[(int)j]+=(long)(k)*(long)(freq.get(k));
 					sum0a[(int)j]%=mod;
 					
 					
 					long prod = (long)(k)*(long)(freq.get(k));
 					prod%=mod;
 					prod*=(long)(k);
 					prod%=mod;
 					sumsqa[(int)j]+=prod;
 					sumsqa[(int)j]%=mod;
 				}
 			}
 		}
 		long complement = 0;
 		mobius[1] = 1;
 		for(long j = 1;j<=100000;j++){
 			if (totaa[(int)j] > 1){
	 			long crossterms = totaa[(int)j]%mod;
	 			crossterms*=power(2, totaa[(int)j]-2L);
	 			crossterms%=mod;
	 			long tempprod = sum0a[(int)j];
	 			tempprod%=mod;
	 			tempprod*=sum0a[(int)j];
	 			tempprod%=mod;
	 			tempprod-=sumsqa[(int)j];
	 			tempprod+=mod;
	 			tempprod%=mod;
	 			crossterms*=tempprod;
	 			crossterms%=mod;
	 			crossterms*=power(2, mod-2);
	 			crossterms%=mod;
	 			long straightterms = (totaa[(int)j]-1L)%mod;
	 			straightterms*=power(2, totaa[(int)j]-2L);
	 			straightterms%=mod;
	 			straightterms*=(sumsqa[(int)j]%mod);
	 			straightterms%=mod;
	 			long sum1 = ((straightterms+crossterms)%mod)*(long)(mobius[(int)j]);
	 			sum1%=mod;
	 			sum1+=mod;
	 			sum1%=mod;
	 			
	 			complement+=sum1;
	 			complement%=mod;
	 			
 			}
 		}
	 	out.println(complement);
 		out.close();	
 	}
	public static int[] mobiusAndPrime(int n){
		int[] isPrime = new int[n+1];
		Arrays.fill(isPrime, 1);
		int[] mu = new int[n+1];
		Arrays.fill(mu,  1);
		for(int i = 2;i<=n;i++){
			if (isPrime[i] == 1){
				for(int j = i;j<=n;j+=i){
					if (j > i)
						isPrime[j] = 0;
					if (j%(i*i) == 0)
						mu[j] = 0;
					mu[j] = -mu[j];
				}
			}
		}
		return mu;
	}
	public static void sort(int[] array){
		ArrayList<Integer> copy = new ArrayList<Integer>();
		for (int i : array)
			copy.add(i);
		Collections.sort(copy);
		for(int i = 0;i<array.length;i++)
			array[i] = copy.get(i);
	}
	static String[] readArrayString(int n){
		String[] array = new String[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.next();
		return array;
	}
	static int[] readArrayInt(int n){
    	int[] array = new int[n];
    	for(int j = 0;j<n;j++)
    		array[j] = sc.nextInt();
    	return array;
    }
	static int[] readArrayInt1(int n){
		int[] array = new int[n+1];
		for(int j = 1;j<=n;j++){
			array[j] = sc.nextInt();
		}
		return array;
	}
	static long[] readArrayLong(int n){
		long[] array = new long[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextLong();
		return array;
	}
	static double[] readArrayDouble(int n){
		double[] array = new double[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextDouble();
		return array;
	}
	static int minIndex(int[] array){
		int minValue = Integer.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(long[] array){
		long minValue = Long.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(double[] array){
		double minValue = Double.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static long power(long x, long y){
		long ans = 1;
		while(y>0){
			if (y%2==1)
				ans = (ans*x)%mod;
			x = (x*x)%mod;
			y/=2;
		}
		return ans;
	}
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            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());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try{
                str = br.readLine();
            } 
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
    }	
}

//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is