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:
// package CodeForces;

import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.InputMismatchException;

public class EducationalRound85E {

//	public static final long maxD = (long)1e15 + 10;
//	public static final int maxL = (int)Math.sqrt(maxD) + 10;
	public static final int max = (int)100;
	public static final long mod = (long)998244353;
//	public static boolean[] isPrime;
	public static long[] fact;
	public static long[] invfact;
	
	public static void Pre() {
//		isPrime = new boolean[maxL];
//		for(long i = 2; i * i <= maxL; i++) {
//			if(!isPrime[(int)i]) {
//				for(long j = i * i; j < maxL; j += i) {
//					isPrime[(int)j] |= true;
//				}
//			}
//		}
		fact = new long[max];
		invfact = new long[max];
		fact[0] = 1;
		invfact[0] = 1;
		for(int i = 1; i < max; i++) {
			fact[i] = (fact[i - 1] * i)%mod;
			invfact[i] = (invfact[i - 1] * ModInverse(i, mod))%mod;
		}
	}
	
	public static void solve() {
//		long time = System.currentTimeMillis();
		Pre();
//		System.out.println(System.currentTimeMillis() - time);
		ArrayList<Long> primes = new ArrayList<Long>();
		long D = s.nextLong();
		for(long i = 2; i * i <= D; i++) {
			if(D%i == 0) {
				while(D%i == 0) {
					D /= i;
				}
				primes.add(i);
			}
		}
		if(D > 1) {
			primes.add(D);
		}
		int q = s.nextInt();
		while(q-- > 0) {
			long a = s.nextLong();
			long b = s.nextLong();
			long g = gcd(a, b);
			long ans = Ways(g, a, primes);
			ans = ans * Ways(g, b, primes);
			ans %= mod;
			out.println(ans);
		}
	}
	
	public static long Ways(long a, long b, ArrayList<Long> primes) { // b >= a
		ArrayList<Integer> counts = new ArrayList<Integer>();
		long dis = b/a;
		for(Long x : primes) {
			int count = 0;
			while(dis%x == 0) {
				dis/=x;
				count++;
			}
			if(count > 0) {
				counts.add(count);
			}
		}
		long ans = 1;
		int sum = 0;
		for(Integer x : counts) {
			ans = (ans * invfact[x])%mod;
			sum += x;
		}
		ans = (ans * fact[sum])%mod;
		return ans;
	}
	
	public static long gcd(long a, long b) {
		if(a == 0) {
			return b;
		}
		return gcd(b%a, a);
	}

	public static void main(String[] args) {
		new Thread(null, null, "Thread", 1 << 27) {
			public void run() {
				try {
					out = new PrintWriter(new BufferedOutputStream(System.out));
					s = new FastReader(System.in);
					solve();
					out.close();
				} catch (Exception e) {
					e.printStackTrace();
					System.exit(1);
				}
			}
		}.start();
	}
	
	public static class Triplet {
		long gcd;
		long x;
		long y;

		Triplet(long gcd, long x, long y) {
			this.gcd = gcd;
			this.x = x;
			this.y = y;
		}
	}

	public static Triplet ExtendedEuclideanAlgo(long a, long b) {
		if (a == 0) {
			return new Triplet(b, 0, 1);
		}
		Triplet ans = ExtendedEuclideanAlgo(b % a, a);
		long x = ans.y - (b / a) * ans.x;
		long y = ans.x;
		return new Triplet(ans.gcd, x, y);
	}

	public static long ModInverse(long a, long m) {
		Triplet ans = ExtendedEuclideanAlgo(a, m);
		if (ans.gcd != 1) {
			throw null;
		} else {
			long result = (ans.x % m + m) % m;
			return result;
		}
	}

	public static PrintWriter out;
	public static FastReader s;

	public static class FastReader {

		private InputStream stream;
		private byte[] buf = new byte[4096];
		private int curChar, snumChars;

		public FastReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (snumChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException E) {
					throw new InputMismatchException();
				}
			}
			if (snumChars <= 0) {
				return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int number = 0;
			do {
				number *= 10;
				number += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			long sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long number = 0;
			do {
				number *= 10L;
				number += (long) (c - '0');
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public int[] nextIntArray(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextLong();
			}
			return arr;
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndofLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndofLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}

	
}