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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class E {

	static long[] facts=new long[1_000_000];
	static long[] factInv=new long[1_000_000];
	static final long mod=998244353;
	
	public static void main(String[] args) {
		precomp();
		FastScanner fs=new FastScanner();
		long D=fs.nextLong();
		ArrayList<Long> primes=PollardRho.getPrimeFactors(D);
		Collections.sort(primes);
		
		TreeSet<Long> uniquePrimes=new TreeSet<>();
		for (long l:primes) uniquePrimes.add(l);
		int nPrimes=uniquePrimes.size();
		HashMap<Long, Integer> compress=new HashMap<>();
		for (long l:uniquePrimes) compress.put(l, compress.size());
		long[] uncompress=new long[nPrimes];
		int index=0;
		for (long l:uniquePrimes) uncompress[index++]=l;
		
		int[] maxCounts=new int[nPrimes];
		for (long l:primes)maxCounts[compress.get(l)]++;
		int[] counts=new int[nPrimes];
		
		HashMap<Long, Long> ans=new HashMap<>();
		while (true) {
			long val=1;
			long nWays=1;
			int totalExps=0;
			for (int i=0; i<nPrimes; i++) {
				totalExps+=counts[i];
				for (int j=0; j<counts[i]; j++)
					val*=uncompress[i];
				nWays=mul(nWays, factInv[counts[i]]);
			}
			nWays=mul(nWays, facts[totalExps]);
			ans.put(val, nWays);
			if (counts.length==0) {
				ans.put(1l, 1l);
				break;
			}
			counts[0]++;
			int digit=0;
			while (digit<nPrimes && counts[digit]>maxCounts[digit]) {
				counts[digit]=0;
				digit++;
				if (digit<nPrimes) counts[digit]++;
			}
			if (digit>=nPrimes) break;
		}
		
		int Q=fs.nextInt();
		PrintWriter out=new PrintWriter(System.out);
		for (int qq=0; qq<Q; qq++) {
			long a=fs.nextLong(), b=fs.nextLong();
			long gcd=gcd(a, b);
			long w1=ans.get(a/gcd);
			long w2=ans.get(b/gcd);
			out.println(mul(w1, w2));
		}
		out.close();
	}
	
	static void precomp() {
		facts[0]=factInv[0]=1;
		for (int i=1; i<facts.length; i++)
			facts[i]=mul(facts[i-1], i);
		factInv[factInv.length-1]=modInv(facts[facts.length-1]);
		for (int i=factInv.length-2; i>=0; i--)
			factInv[i]=mul(factInv[i+1], i+1);
	}
	
	static long mul(long a, long b) {
		return a*b%mod;
	}
	
	static long modInv(long x) {
		return pow(x, mod-2);
	}
	
	static long pow(long base, long exp) {
		if (exp==0) return 1;
		long half=pow(base, exp/2);
		if (exp%2==0) return mul(half, half);
		return mul(half, mul(half, base));
	}

	static long gcd(long a, long b) {
		return b==0?a:gcd(b, a%b);
	}
	
	static class PollardRho {
		static Random r=new Random();

		static ArrayList<Long> getPrimeFactors(long n) {
			ArrayList<Long> factors=new ArrayList<>();
			getPrimeFactors(n, factors);
			// Collections.sort(factors); if you want multiplicities in a row
			return factors;
		}

		static void getPrimeFactors(long n, ArrayList<Long> factors) {
			if (n<=1) {
			} else if (BigInteger.valueOf(n).isProbablePrime(30))
				factors.add(n);
			else {
				long d=rho(n);
				getPrimeFactors(d, factors);
				getPrimeFactors(n/d, factors);
			}
		}

		// returns a small non-trivial divisor of n (n must not be prime)
		static long rho(long n) {
			if (n<=3)
				return -1;
			if ((n&1)==0)
				return 2;
			long x, y, d;
			BigInteger ab, nb;

			nb=BigInteger.valueOf(n);
			do {
				ab=BigInteger.valueOf(Math.abs(r.nextInt(100_000))+2);
				x=y=Math.abs(r.nextInt(100_000))+2;
				do {
					x=poly(x, ab, nb);
					y=polypoly(y, ab, nb);
					d=gcd(n, Math.abs(x-y));
				} while (d==1);
			} while (d==n);
			return d;
		}

		
		
		static long poly(long x, BigInteger ab, BigInteger nb) {
			BigInteger xb=BigInteger.valueOf(x);
			return xb.multiply(xb).add(ab).mod(nb).longValue();
		}

		static long polypoly(long x, BigInteger ab, BigInteger nb) {
			BigInteger xb=BigInteger.valueOf(x), p=xb.multiply(xb).add(ab);
			return p.multiply(p).add(ab).mod(nb).longValue();
		}
	}

	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");

		public String next() {
			while (!st.hasMoreElements())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) {
				a[i]=nextInt();
			}
			return a;
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

	}

}