Problem: You are given a positive integer D. Let's build the following graph from it: 

  * each vertex is a divisor of D (not necessarily prime, 1 and D itself are also included); 
  * two vertices x and y (x > y) have an undirected edge between them if x is divisible by y and \frac x y is a prime; 
  * the weight of an edge is the number of divisors of x that are not divisors of y. 



For example, here is the graph for D=12: 

<image>

Edge (4,12) has weight 3 because 12 has divisors [1,2,3,4,6,12] and 4 has divisors [1,2,4]. Thus, there are 3 divisors of 12 that are not divisors of 4 — [3,6,12].

There is no edge between 3 and 2 because 3 is not divisible by 2. There is no edge between 12 and 3 because 12/3=4 is not a prime.

Let the length of the path between some vertices v and u in the graph be the total weight of edges on it. For example, path [(1, 2), (2, 6), (6, 12), (12, 4), (4, 2), (2, 6)] has length 1+2+2+3+1+2=11. The empty path has length 0.

So the shortest path between two vertices v and u is the path that has the minimal possible length.

Two paths a and b are different if there is either a different number of edges in them or there is a position i such that a_i and b_i are different edges.

You are given q queries of the following form: 

  * v u — calculate the number of the shortest paths between vertices v and u. 



The answer for each query might be large so print it modulo 998244353.

Input

The first line contains a single integer D (1 ≤ D ≤ 10^{15}) — the number the graph is built from.

The second line contains a single integer q (1 ≤ q ≤ 3 ⋅ 10^5) — the number of queries.

Each of the next q lines contains two integers v and u (1 ≤ v, u ≤ D). It is guaranteed that D is divisible by both v and u (both v and u are divisors of D).

Output

Print q integers — for each query output the number of the shortest paths between the two given vertices modulo 998244353.

Examples

Input


12
3
4 4
12 1
3 4


Output


1
3
1


Input


1
1
1 1


Output


1


Input


288807105787200
4
46 482955026400
12556830686400 897
414 12556830686400
4443186242880 325


Output


547558588
277147129
457421435
702277623

Note

In the first example: 

  * The first query is only the empty path — length 0; 
  * The second query are paths [(12, 4), (4, 2), (2, 1)] (length 3+1+1=5), [(12, 6), (6, 2), (2, 1)] (length 2+2+1=5) and [(12, 6), (6, 3), (3, 1)] (length 2+2+1=5). 
  * The third query is only the path [(3, 1), (1, 2), (2, 4)] (length 1+1+1=3). 

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
public class Ed85E {
 
	public static void main(String[] args) throws Exception{
		int num = 998244353;
		// TODO Auto-generated method stub
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter out = new PrintWriter(System.out);
 		long[] fact = new long[51];
 		fact[0] = 1;
 		long ans1 = 1;
 		for(int i = 1;i<=50;i++){
 			ans1= (ans1*i) % num;
 			fact[i] = ans1;
 		}
 		long[] inv = new long[51];
 		inv[0] = 1;
 		for(int i = 1;i<=50;i++){
 			inv[i] = power(fact[i], num-2, num)%num;
 		}
 		long d = Long.parseLong(bf.readLine());
 		Map<Long, Integer> d1 = factorize(d);
 		int q = Integer.parseInt(bf.readLine());
 		for(int i = 0;i<q;i++){
 			StringTokenizer st = new StringTokenizer(bf.readLine());
 			long a = Long.parseLong(st.nextToken());
 			long b = Long.parseLong(st.nextToken());
 			ArrayList<Integer> decrease = new ArrayList<>();
 			ArrayList<Integer> increase = new ArrayList<>();
 			int increasesum = 0;
 			int decreasesum = 0;
 			long decreaseprod = 1;
 			long increaseprod = 1;
 			for(long k: d1.keySet()){
 				int counta = 0;
 				while (a%k == 0){
 					a/=k;
 					counta+=1;
 				}
 				
 				int countb = 0;
 				while (b%k == 0){
 					b/=k;
 					countb+=1;
 				}
 				
 				if (counta > countb){
 					decrease.add(counta-countb);
 					decreaseprod = (decreaseprod * inv[counta-countb]) %num;
 					decreasesum+= (counta-countb);
 				}
 				else if (countb > counta){
 					increase.add(countb-counta);
 					increaseprod = (increaseprod * inv[countb-counta]) %num;
 					increasesum+= countb-counta;
 				}
 				
 				
 			}
 			
 			long ans = 1;
 			decreaseprod = (decreaseprod* fact[decreasesum])%num;
 			increaseprod  = (increaseprod* fact[increasesum])%num;
 			ans = (increaseprod * decreaseprod) % num;
 			out.println(ans);
 			
 			
 			
 		}
 		
 		
 		
 		
 		out.close();
 		
 		
 		
 		
	}
	
	public static int power(long x, long y, long mod){
		long ans = 1;
		while(y>0){
			if (y%2==1)
				ans = (ans*x)%mod;
			x = (x*x)%mod;
			y/=2;
		}
		return (int)(ans);
	}
	
	 public static Map<Long, Integer> factorize(long n) { 
		 	Map<Long, Integer> pf = new HashMap<Long, Integer>();
	        int count = 0; 
	  
	        // count the number of times 2 divides  
	        while (!(n % 2 > 0)) { 
	            // equivalent to n=n/2;  
	            n >>= 1; 
	  
	            count++; 
	        } 
	  
	        // if 2 divides it  
	        if (count > 0) { 
	            pf.put((long)(2) , count);
	        } 
	  
	        // check for all the possible  
	        // numbers that can divide it  
	        for (long i = 3; i <= (long) Math.sqrt(n); i += 2) { 
	            count = 0; 
	            while (n % i == 0) { 
	                count++; 
	                n = n / i; 
	            } 
	            if (count > 0) { 
	                pf.put(i, count);
	            } 
	        } 
	  
	        // if n at the end is a prime number.  
	        if (n > 2) { 
	           pf.put(n, 1);
	        } 
	        return pf;
	    }
	
	
 
 }
	
 	
// 
////StringJoiner sj = new StringJoiner(" "); 
////sj.add(strings)
////sj.toString() gives string of those stuff w spaces or whatever that sequence is
//class BinaryIndexedTree 
//{  
//    // Max tree size 
//    final static int MAX = 1000005;      
//  
//    static int BITree[] = new int[MAX];     
//    /* n --> No. of elements present in input array.  
//    BITree[0..n] --> Array that represents Binary  
//                    Indexed Tree. 
//    arr[0..n-1] --> Input array for which prefix sum  
//                    is evaluated. */
//  
//    // Returns sum of arr[0..index]. This function  
//    // assumes that the array is preprocessed and  
//    // partial sums of array elements are stored  
//    // in BITree[]. 
//    int getSum(int index){ 
//        int sum = 0;
//        index = index + 1; 
//        while(index>0){ 
//            sum += BITree[index]; 
//            index -= index & (-index); 
//        } 
//        return sum; 
//    } 
//    public static void updateBIT(int n, int index, int val){ 
//        index = index + 1; 
//        while(index <= n){ 
//	        BITree[index] += val; 
//	        index += index & (-index); 
//        } 
//    } 
//    void constructBITree(int arr[], int n){ 
//        for(int i=1; i<=n; i++) 
//            BITree[i] = 0; 
//        for(int i = 0; i < n; i++) 
//            updateBIT(n, i, arr[i]); 
//    } 
//}