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.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
public class E {
	 public static ArrayList<Long> primeFactors(long n) 
	    { 
		 ArrayList<Long>res = new ArrayList<Long>();
	        while (n%2==0) 
	        { 
	           res.add(2l); 
	            n /= 2; 
	        } 
	        for (int i = 3; i <= Math.sqrt(n); i+= 2) 
	        {
	            while (n%i == 0) 
	            { 
	                res.add((long)i); 
	                n /= i; 
	            } 
	        } 
	        if (n > 2) 
	            res.add(n);
	        return res;
	    }
	 static final int MAXN = 100001;
	 static ArrayList<Long> factors;
     
	    
	 public static long A = 998244353l;
	 public static long fact(long n) {
		 long res =1;
		 for(int i=2;i<=n;i++) {
			 res *= i;
			 res %=A;
		 }
		 return res;
	 }
	 public static ArrayList<Long> getFactors(long x){
		 int i =0;
		 ArrayList<Long>res = new ArrayList<Long>();
		 while(x>1) {
			 if(x%factors.get(i)==0) {
				 x/=factors.get(i);
				 res.add(factors.get(i));
			 }
			 i++;
		 }
		 return res;
	 }
public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	//BufferedReader br = new BufferedReader(new FileReader(new File("src/test.txt")));
	Scanner sc = new Scanner(System.in);
	PrintWriter pw = new PrintWriter(System.out);
	
	long x = Long.parseLong(br.readLine());
	factors = primeFactors(x);
	int q = Integer.parseInt(br.readLine());
	while(q-->0) {
		String[]in = br.readLine().split(" ");
	long a = Long.parseLong(in[0]);
	long b = Long.parseLong(in[1]);
	if(b>a) {
		long tmp = b;
		b = a; 
		a = tmp;
	}
	// a is always bigger than b
	ArrayList<Long> res2 = new ArrayList<Long>();
	ArrayList<Long> arr1 = getFactors(a);
	ArrayList<Long> arr2 = getFactors(b);
	ArrayList<Long> res = new ArrayList<Long>();

	for(int i=0,j=0;i<arr1.size();) {
		if(j>=arr2.size()) {
			res.add(arr1.get(i));
			i++;
			continue;
		}
		if(arr2.get(j)>arr1.get(i)) {
			res.add(arr1.get(i));
			i++;
		}else if(arr2.get(j)<arr1.get(i)){
			j++;
		}else {
			i++;j++;
		}
	}
	for(int i=0,j=0;i<arr2.size();) {
		if(j>=arr1.size()) {
			res2.add(arr2.get(i));
			i++;
			continue;
		}
		if(arr1.get(j)>arr2.get(i)){
			res2.add(arr2.get(i));
			i++;
		}else if(arr1.get(j)<arr2.get(i)){
			j++;
		}else {
			i++;j++;
		}
	}
	long r = (fact(res.size()));
	r %=A;
	int c = 1;
	for(int i=0;i<res.size()-1;i++) {
		if(res.get(i)!=res.get(i+1)) {
			//System.out.println(c);
			BigInteger cd = new BigInteger(fact(c)+"");
			long tt = cd.modInverse(new BigInteger(A+"")).longValue();
			r *=tt;
			r %=A;
			c = 1;
		}else {
			c++;
		}
	}
	BigInteger cd = new BigInteger(fact(c)+"");
	long tt = cd.modInverse(new BigInteger(A+"")).longValue();
	r *=tt;
	r %=A;
	c = 1;
	r*= fact(res2.size());
	r%=A;
	for(int i=0;i<res2.size()-1;i++) {
		if(res2.get(i)!=res2.get(i+1)) {
			BigInteger cd1 = new BigInteger(fact(c)+"");
			long tt1 = cd1.modInverse(new BigInteger(A+"")).longValue();
			r *=tt1;
			r %=A;
			c = 1;
		}else {
			c++;
		}
	}
	BigInteger cd1 = new BigInteger(fact(c)+"");
	long tt1 = cd1.modInverse(new BigInteger(A+"")).longValue();
	r *=tt1;
	r %=A;
	c = 1;
	
	pw.println(r);
	}
	pw.flush();
	pw.close();
}
}