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.*;
import java.util.zip.Adler32;

public class Contest1 {
    static int mod=998244353;
    static long[]fac;
    static long modPow(long a,int e, int mod)	// O(log e)
    {
        a %= mod;
        long res = 1;
        while(e > 0)
        {
            if((e & 1) == 1)
                res = (res * a) % mod;
            a = (a * a) % mod;
            e >>= 1;
        }
        return res;
    }

    static int[] fac(long x,ArrayList<Long> divs){
        int[]ret= new int[divs.size()];
        for (int i =0;i<divs.size();i++){
            long p = divs.get(i);
            int e =0;
            while (x%p==0){
                x/=p;
                e++;
            }
            ret[i]=e;
        }
        return ret;
    }
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        long d = sc.nextLong();
        ArrayList<Long> divs = new ArrayList<>();
        long c = d;
        for (long i =2;i*i<=d;i++){
            if (c%i==0){
                divs.add(i);
                while (c%i==0)
                    c/=i;
            }
        }
        if (c!=1)
            divs.add(c);
        int q = sc.nextInt();
        fac= new long[201];
        fac[0]=fac[1]=1;
        for (int i =2;i<=200;i++){
            fac[i]=(i*fac[i-1])%mod;
        }
        long[]inv = new long[201];
        for (int i =0;i<=200;i++)inv[i]=modPow(fac[i],mod-2,mod);
        while (q-->0){
            long u = sc.nextLong();
            long v = sc.nextLong();
            int[] d1= fac(u,divs),d2=fac(v,divs);
            int all1 =0;
            int all2 =0;
            ArrayList<Integer>def= new ArrayList<>(divs.size());
            for (int i =0;i<divs.size();i++){
                int cur =Math.abs(d1[i]-d2[i]);
                if (d1[i]<=d2[i]) {
                    all1 += cur;
                }
                else all2+=cur;
                def.add(cur);
            }
            long ans = fac[all1]*fac[all2];
            ans%=mod;
            for (int x:def){
                ans*=inv[x];
                ans%=mod;
            }
            pw.println(ans);
        }
        pw.flush();
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

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

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }

}