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:
/**
 * @author derrick20
 */
import java.io.*;
import java.util.*;

public class DivisorPaths {
//    static long[] primes = new long[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43};
    static long mod = 998244353;
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        long D = sc.nextLong();
        factors = new HashMap<>();
        long curr = D;
        for (long i = 2; i * i <= D; i++) {
            if (curr % i == 0) {
                while (curr % i == 0) {
                    factors.merge(i, 1, Integer::sum);
                    curr /= i;
                }
            }
        }
        if (curr > 1) {
            factors.merge(curr, 1, Integer::sum);
        }
//        System.out.println(factors);

        // can't be that many powers (2^50 is 10^15 already!)
        fact = new long[100];
        factInv = new long[100];
        fact[0] = 1;
        factInv[0] = 1;
        for (int i = 1; i < fact.length; i++) {
            fact[i] = ((long) i * fact[i - 1]) % mod;
            factInv[i] = fastExpo(fact[i], mod - 2);
        }

//        System.out.println(factors);
        int Q = sc.nextInt();
        while (Q-->0) {
            long u = sc.nextLong();
            long v = sc.nextLong();
            long g = gcd(u, v);
            u /= g;
            v /= g;
            long ans = (paths(u, 1) * paths(v, 1)) % mod;
            out.println(ans);
        }

        out.close();
    }
    /*
866421317361600
20
394571100 4633269076800
251160 25362136800
5348279736800 16965
22724 4247163320400
79089525 14256212544
2768688 521664
456961700 268107840
6942600 65340974160
6566285088 8099091
719987400 54621504
3880077552 28231388640
1482741 4468464
316999800 53255966400
90090 232908956280
3025512 248820
3652110 24067680
4494352720 2012868
77895972 4064271120
345345 1432600
1175720 5312160
2772725670 112117824
64096032 475499700
8058204 6908970
98423325 132177165120
     */

    static long[] fact, factInv;
    static HashMap<Long, Integer> factors;

    static long paths(long u, long v) {
        if (u < v) {
            long temp = u;
            u = v;
            v = temp;
        }
        // u > v now
        long val = u / v;
        HashMap<Long, Integer> myFactors = new HashMap<>();
        int total = 0;
        for (long f : factors.keySet()) {
            // all the factors MUST have been accounted for by now
            if (val % f == 0) {
                while (val % f == 0) {
                    myFactors.merge(f, 1, Integer::sum);
                    total++;
                    val /= f;
                }
            }
        }
//        System.out.println(myFactors);
        long ans = fact[total];
        for (int amt : myFactors.values()) {
            ans = (ans * factInv[amt]) % mod;
        }
        return ans;
    }

    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    static long fastExpo(long x, long k) {
        if (k == 0) {
            return 1;
        }
        else if (k == 1) {
            return x;
        }
        else {
            long root = fastExpo(x, k / 2);
            long ans = (root * root) % mod;
            if (k % 2 == 1) {
                ans = (ans * x) % mod;
            }
            return ans;
        }
    }

    static class FastScanner {
        private int BS = 1<<16;
        private char NC = (char)0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            }
            catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar(){
            while(bId==size) {
                try {
                    size = in.read(buf);
                }catch(Exception e) {
                    return NC;
                }
                if(size==-1)return NC;
                bId=0;
            }
            return (char)buf[bId++];
        }

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

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt=1;
            boolean neg = false;
            if(c==NC)c=getChar();
            for(;(c<'0' || c>'9'); c = getChar()) {
                if(c=='-')neg=true;
            }
            long res = 0;
            for(; c>='0' && c <='9'; c=getChar()) {
                res = (res<<3)+(res<<1)+c-'0';
                cnt*=10;
            }
            return neg?-res:res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c!='.' ? cur:cur+nextLong()/cnt;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c>32) {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c!='\n') {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if(c>32)return true;
            while(true) {
                c=getChar();
                if(c==NC)return false;
                else if(c>32)return true;
            }
        }
    }
}