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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.Locale;
import java.util.StringTokenizer;

public class Solution implements Runnable {
	
	public static final int MOD = 998244353;
	
	private PrintStream out;
	private BufferedReader in;
	private StringTokenizer st;
	
	public void solve() throws IOException {
		long time0 = System.currentTimeMillis();
		
		long d = nextLong();
		int q = nextInt();
		long[] u = new long[q];
		long[] v = new long[q];
		for (int i = 0; i < q; i++) {
			u[i] = nextLong();
			v[i] = nextLong();
		}
		int[] answer = solve(d, q, u, v);
		for (int i = 0; i < answer.length; i++) {
			out.println(answer[i]);
		}
		
		System.err.println("time: " + (System.currentTimeMillis() - time0));
	}
	
	private int[] solve(long d, int q, long[] u, long[] v) {
		long[] primes = primes(d);
		int[][] cnk = precalcCnk(d, primes);
		int[] answer = new int[q];
		for (int i = 0; i < q; i++) {
			answer[i] = solve(factorize(u[i], primes), factorize(v[i], primes), cnk);
		}
		return answer;
	}
	
	private int[][] precalcCnk(long d, long[] primes) {
		int[] df = factorize(d, primes);
		int sum = 0;
		for (int i = 0; i < df.length; i++) {
			sum += df[i];
		}
		int[][] c = new int[sum + 1][sum + 1];
		c[0][0] = 1;
		for (int n = 1; n <= sum; n++) {
			c[n][0] = 1;
			for (int k = 1; k <= sum; k++) {
				c[n][k] = (c[n - 1][k] + c[n - 1][k - 1]) % MOD;
			}
		}
		return c;
	}

	private int[] factorize(long u, long[] primes) {
		int[] result = new int[primes.length];
		for (int i = 0; i < primes.length; i++) {
			while ((u % primes[i]) == 0) {
				u /= primes[i];
				result[i]++;
			}
		}
		return result;
	}

	private int solve(int[] u, int[] v, int[][] cnk) {
		for (int i = 0; i < u.length; i++) {
			int gcd = Math.min(u[i], v[i]);
			u[i] -= gcd;
			v[i] -= gcd;
		}
		return mult(solve(u, cnk), solve(v, cnk));
	}

	private int solve(int[] u, int[][] cnk) {
		int result = 1;
		int sum = 0;
		for (int i = 0; i < u.length; i++) {
			sum += u[i];
			result = mult(result, cnk[sum][u[i]]);
		}
		return result;
	}

	private int mult(int a, int b) {
		return (int) ((1L * a * b) % MOD);
	}

	private long[] primes(long d) {
		int cap = (int) Math.sqrt(d);
		while (1L * cap * cap <= d) {
			cap++;
		}
		boolean[] s = new boolean[cap];
		for (int i = 2; i * i < cap; i++) {
			if (!s[i]) {
				for (int j = 2; j * i < cap; j++) {
					s[j * i] = true;
				}
			}
		}
		int cnt = 0;
		long rem = d;
		for (int i = 2; i < cap; i++) {
			if (!s[i] && ((d % i) == 0)) {
				cnt++;
				while ((rem % i) == 0) {
					rem /= i;
				}
			}
		}
		if (rem > 1) {
			cnt++;
		}
		long[] result = new long[cnt];
		cnt = 0;
		for (int i = 2; i < cap; i++) {
			if (!s[i] && ((d % i) == 0)) {
				result[cnt++] = i;
			}
		}
		if (rem > 1) {
			result[cnt++] = rem;
		}
		return result;
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
	
	public long nextLong() throws IOException {
		return Long.parseLong(next());
	}
	
	public int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
	
	public String next() throws IOException {
		while (!st.hasMoreTokens()) {
			String line = in.readLine();
			if (line == null) {
				return null;
			}
			st = new StringTokenizer(line);
		}
		return st.nextToken();
	}
	
	@Override
	public void run() {
		try {
			solve();
			out.close();
		} catch (Throwable e) {
			throw new RuntimeException(e);
		}
	}
	
	public Solution(String name) throws IOException {
		Locale.setDefault(Locale.US);
		if (name == null) {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintStream(new BufferedOutputStream(System.out));
		} else {
			in = new BufferedReader(new InputStreamReader(new FileInputStream(name + ".in")));
			out = new PrintStream(new BufferedOutputStream(new FileOutputStream(name + ".out")));
		}
		st = new StringTokenizer("");
	}
	
	public static void main(String[] args) throws IOException {
		new Thread(new Solution(null)).start();
	}
}