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.*;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
	static FastScanner sc = new FastScanner(System.in);
	static final long MOD = 998244353;

	public static void main(String[] args) {
		long[] fact = new long[1000];
		long[] factInv = new long[fact.length];
		fact[0] = factInv[0] = 1;
		for (int i = 1; i < fact.length; i++) {
			fact[i] = fact[i - 1] * i % MOD;
		}
		factInv[fact.length - 1] = inv(fact[fact.length - 1]);
		for (int i = fact.length - 1; i > 0; i--) {
			factInv[i - 1] = factInv[i] * i % MOD;
		}
		long D = sc.nextLong();
		ArrayList<Long> p = new ArrayList<>();
		ArrayList<Integer> c = new ArrayList<>();
		for (long i = 2; i * i <= D; i++) {
			if (D % i == 0) {
				p.add(i);
				int n = 1;
				D /= i;
				while (D % i == 0) {
					D /= i;
					n++;
				}
				c.add(n);
			}
		}
		if (D != 1) {
			p.add(D);
			c.add(1);
		}
		int Q = sc.nextInt();
		long[] c1 = new long[c.size()];
		long[] c2 = new long[c.size()];
		PrintWriter writer = new PrintWriter(System.out);
		for (int i = 0; i < Q; i++) {
			Arrays.fill(c1, 0);
			Arrays.fill(c2, 0);
			long v = sc.nextLong();
			long u = sc.nextLong();
			if (v == u) {
				writer.println(1);
				continue;
			}
			long vt = v;
			long ut = u;
			long s1 = 1;
			long s2 = 1;
			long upper = 1;
			long lower = 1;
			for (int j = 0; j < p.size(); j++) {
				long prime = p.get(j);
				while (vt % prime == 0) {
					vt /= prime;
					c1[j]++;
				}
				s1 *= (c1[j] + 1);
				while (ut % prime == 0) {
					ut /= prime;
					c2[j]++;
				}
				s2 *= (c2[j] + 1);
				upper *= Math.max(c1[j], c2[j]) + 1;
				lower *= Math.min(c1[j], c2[j]) + 1;
			}
			boolean one = upper == s1 || upper == s2;
			long nl = s1 + s2 - 2 * lower;
			long nu = 2 * upper - s1 - s2;
			long ans = 0;
//			System.err.println(s1 + " " + s2 + " " + lower + " " + upper + " " + nl + " " + nu);
			if (nl <= nu) {
				long ansl = 1;
				long sum1 = 0;
				long sum2 = 0;
				for (int j = 0; j < p.size(); j++) {
					long cc = c1[j] - Math.min(c1[j], c2[j]);
					sum1 += cc;
					ansl *= factInv[(int) cc];
					ansl %= MOD;
					cc = c2[j] - Math.min(c1[j], c2[j]);
					sum2 += cc;
					ansl *= factInv[(int) cc];
					ansl %= MOD;
				}
				ansl *= fact[(int) sum1];
				ansl %= MOD;
				ansl *= fact[(int) sum2];
				ansl %= MOD;
				ans += ansl;
			}
			if (nu <= nl && !one) {
				long ansu = 1;
				long sum1 = 0;
				long sum2 = 0;
				for (int j = 0; j < p.size(); j++) {
					long cc = Math.max(c1[j], c2[j]) - c1[j];
					sum1 += cc;
					ansu *= factInv[(int) cc];
					ansu %= MOD;
					cc = Math.max(c1[j], c2[j]) - c2[j];
					sum2 += cc;
					ansu *= factInv[(int) cc];
					ansu %= MOD;
				}
				ansu *= fact[(int) sum1];
				ansu %= MOD;
				ansu *= fact[(int) sum2];
				ansu %= MOD;
				ans += ansu;
			}
			writer.println(ans);
		}
		writer.flush();
	}

	static long inv(long v) {
		return pow(v, MOD - 2);
	}

	static long pow(long b, long p) {
		if (p == 0) return 1;
		if (p == 1) return b;
		long ret = pow(b, p / 2);
		ret *= ret;
		ret %= MOD;
		if (p % 2 == 1) {
			ret *= b;
			ret %= MOD;
		}
		return ret;
	}

	static class FastScanner {
		Reader input;

		FastScanner() {
			this(System.in);
		}

		FastScanner(InputStream stream) {
			this.input = new BufferedReader(new InputStreamReader(stream));
		}

		int nextInt() {
			return (int) nextLong();
		}

		long nextLong() {
			try {
				int sign = 1;
				int b = input.read();
				while ((b < '0' || '9' < b) && b != '-' && b != '+') {
					b = input.read();
				}
				if (b == '-') {
					sign = -1;
					b = input.read();
				} else if (b == '+') {
					b = input.read();
				}
				long ret = b - '0';
				while (true) {
					b = input.read();
					if (b < '0' || '9' < b) return ret * sign;
					ret *= 10;
					ret += b - '0';
				}
			} catch (IOException e) {
				e.printStackTrace();
				return -1;
			}
		}

		double nextDouble() {
			try {
				double sign = 1;
				int b = input.read();
				while ((b < '0' || '9' < b) && b != '-' && b != '+') {
					b = input.read();
				}
				if (b == '-') {
					sign = -1;
					b = input.read();
				} else if (b == '+') {
					b = input.read();
				}
				double ret = b - '0';
				while (true) {
					b = input.read();
					if (b < '0' || '9' < b) break;
					ret *= 10;
					ret += b - '0';
				}
				if (b != '.') return sign * ret;
				double div = 1;
				b = input.read();
				while ('0' <= b && b <= '9') {
					ret *= 10;
					ret += b - '0';
					div *= 10;
					b = input.read();
				}
				return sign * ret / div;
			} catch (IOException e) {
				e.printStackTrace();
				return Double.NaN;
			}
		}

		char nextChar() {
			try {
				int b = input.read();
				while (Character.isWhitespace(b)) {
					b = input.read();
				}
				return (char) b;
			} catch (IOException e) {
				e.printStackTrace();
				return 0;
			}
		}

		String nextStr() {
			try {
				StringBuilder sb = new StringBuilder();
				int b = input.read();
				while (Character.isWhitespace(b)) {
					b = input.read();
				}
				while (b != -1 && !Character.isWhitespace(b)) {
					sb.append((char) b);
					b = input.read();
				}
				return sb.toString();
			} catch (IOException e) {
				e.printStackTrace();
				return "";
			}
		}

	}
}