Problem: Well, here is another math class task. In mathematics, GCD is the greatest common divisor, and it's an easy task to calculate the GCD between two positive integers.

A common divisor for two positive numbers is a number which both numbers are divisible by.

But your teacher wants to give you a harder task, in this task you have to find the greatest common divisor d between two integers a and b that is in a given range from low to high (inclusive), i.e. low ≤ d ≤ high. It is possible that there is no common divisor in the given range.

You will be given the two integers a and b, then n queries. Each query is a range from low to high and you have to answer each query.

Input

The first line contains two integers a and b, the two integers as described above (1 ≤ a, b ≤ 109). The second line contains one integer n, the number of queries (1 ≤ n ≤ 104). Then n lines follow, each line contains one query consisting of two integers, low and high (1 ≤ low ≤ high ≤ 109).

Output

Print n lines. The i-th of them should contain the result of the i-th query in the input. If there is no common divisor in the given range for any query, you should print -1 as a result for this query.

Examples

Input

9 27
3
1 5
10 11
9 11


Output

3
-1
9

Solution (in JAVA):

Solution:

import javax.swing.plaf.basic.BasicTreeUI;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;


public class Main {
    private static Scanner sc;
    private static Printer pr;
    static boolean []visited;
    static int []color;
    static int []pow=new int[(int)3e5+1];
    static int []count;
    static boolean check=true;
    static boolean checkBip=true;
    static TreeSet<Integer>[]list;
    private static long aLong=(long)(Math.pow(10,9)+7);
    static final long div=998244353;
    static  int answer=0;
    static int[]countSubTree;
    static int[]colorNode;
    static boolean con=true;
    static ArrayList<Integer>dfsPath=new ArrayList<>();
    static ArrayList<Integer>ans=new ArrayList<>();
    static boolean[]rec;
    static int min=Integer.MAX_VALUE;
    static ArrayList<Task>tasks=new ArrayList<>();
    private static void solve() throws IOException {
        long a=sc.nextLong(),b=sc.nextLong();
        long gcd=gcd(a,b);
        TreeSet<Long>list=new TreeSet<>();
        for (long i=1;i*i<=gcd;++i){
            if (gcd%i==0){
                if (gcd/i==i)list.add(i);
                else{
                    list.add(i);
                    list.add(gcd/i);
                }
            }
        }
        int q=sc.nextInt();
        for (int i=1;i<=q;++i){
            long low=sc.nextLong(),high=sc.nextLong();
            if (low>gcd){
                pr.println(-1);
                continue;
            }
            if (list.floor(high)!=null){
                long num=list.floor(high);
                if (num>=low){
                    pr.println(num);
                    continue;
                }
                else{
                    pr.println(-1);
                    continue;
                }
            }
            pr.println(-1);
        }

    }
    public static class Task{
        int head;
        int tail;
        public Task(int   w,int v) {
            this.head = w;
            this.tail=v;
        }
    }
    public static void printSolve(StringBuilder str, int[] colors, int n,int color){
        for(int i = 1;i<=n;++i)
            if(colors[i] == color)
                str.append(i + " ");
        str.append('\n');
    }
    public static class pairTask{
        int  val;
        int size;
        public pairTask(int   x, int  y) {
            this.val = x;
            this.size = y;
        }
    }
    public static void subTree(int src,int parent){
        countSubTree[src]=1;
        for (int v:list[src]){
            if (v==parent)
                continue;
            subTree(v,src);
            countSubTree[src]+=countSubTree[v];
        }
    }
    public static boolean prime(long src){
        for (int i=2;i*i<=src;i++){
            if (src%i==0)
                return false;
        }
        return true;
    }
    public static void bfsColor(int src){
        Queue<Integer>queue = new ArrayDeque<>();
        queue.add(src);
        while (!queue.isEmpty()){
            boolean b=false;
            int vertex=-1,p=-1;
            int poll=queue.remove();
            for (int v:list[poll]){
                if (color [v]==0){
                    vertex=v;
                    break;
                }
            }
            for (int v:list[poll]){
                if (color [v]!=0&&v!=vertex){
                    p=v;
                    break;
                }
            }
            for (int v:list[p]){
                if (color [v]!=0){
                    color[vertex]=color[v];
                    b=true;
                    break;
                }
            }
            if (!b){
                color[vertex]=color[poll]+1;
            }
        }
    }
    static int add(int a,int b ){
        if (a+b>=div)
            return (int)(a+b-div);
        return (int)a+b;
    }
    public static int isBipartite(ArrayList<Integer>[]list,int src){
        color[src]=0;
        Queue<Integer>queue=new LinkedList<>();
        int []ans={0,0};
        queue.add(src);
        while (!queue.isEmpty()){
            ans[color[src=queue.poll()]]++;
            for (int v:list[src]){
                if (color[v]==-1){
                    queue.add(v);
                    color[v]=color[src]^1;
                }else if (color[v]==color[src])
                    check=false;
            }
        }
        return add(pow[ans[0]],pow[ans[1]]);
    }
    public static int powerMod(long b, long e){
        long ans=1;
        while (e-->0){
            ans=ans*b%div;
        }
        return (int)ans;
    }
    public static int dfs(int s){
        int ans=1;
        visited[s]=true;
        for (int k:list[s]){
            if (!visited[k]){
                ans+=dfs(k);
            }
        }
        return ans;
    }
    public static int[] radixSort(int[] f) {
        int[] to = new int[f.length];
        {
            int[] b = new int[65537];
            for (int i = 0; i < f.length; i++) b[1 + (f[i] & 0xffff)]++;
            for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
            for (int i = 0; i < f.length; i++) to[b[f[i] & 0xffff]++] = f[i];
            int[] d = f;
            f = to;
            to = d;
        }
        {
            int[] b = new int[65537];
            for (int i = 0; i < f.length; i++) b[1 + (f[i] >>> 16)]++;
            for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
            for (int i = 0; i < f.length; i++) to[b[f[i] >>> 16]++] = f[i];
            int[] d = f;
            f = to;
            to = d;
        }
        return f;
    }
    public static long []primeFactor(int n){
        long []prime=new long[n+1];
        prime[1]=1;
        for (int i=2;i<=n;i++)
            prime[i]=((i&1)==0)?2:i;
        for (int i=3;i*i<=n;i++){
            if (prime[i]==i){
                for (int j=i*i;j<=n;j+=i){
                    if (prime[j]==j)
                        prime[j]=i;
                }
            }
        }
        return prime;
    }
    public static StringBuilder binaryradix(long number){
        StringBuilder builder=new StringBuilder();
        long remainder;
        while (number!=0) {
            remainder = number % 2;
            number >>= 1;
            builder.append(remainder);
        }
        builder.reverse();
        return builder;
    }
    public static int binarySearch(long[] a, int index,long target) {
            int l = index;
            int h = a.length - 1;
            while (l<=h) {
                int med = l + (h-l)/2;
                if(a[med] - target <= target) {
                    l = med + 1;
                }
                else h = med  - 1;
            }
            return h;
    }
    public static int val(char c){
        return c-'0';
    }
    public static long gcd(long a,long b) {
        if (a == 0) return b;
        return gcd(b % a, a);
    }
        private static class Pair implements Comparable<Pair> {
            long x;
            long y;

            Pair() {
                this.x = 0;
                this.y = 0;
            }

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

            @Override
            public boolean equals(Object obj) {
                if (this == obj) {
                    return true;
                }
                if (obj == null) return false;
                Pair other = (Pair) obj;
                if (this.x == other.x && this.y == other.y) {
                    return true;
                }
                return false;
            }

            @Override
            public int compareTo(Pair other) {
                if (this.x != other.x) return Long.compare(this.x, other.x);
                return Long.compare(this.y*other.x, this.x*other.y);
            }
    }

    public static void main(String[] args) throws IOException {
        sc = new Scanner(System.in);
        pr = new Printer(System.out);
        solve();

        pr.close();
       // sc.close();
    }
    private static class Scanner {
        BufferedReader br;

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

        private boolean isPrintable(int ch) {
            return ch >= '!' && ch <= '~';
        }

        private boolean isCRLF(int ch) {
            return ch == '\n' || ch == '\r' || ch == -1;
        }

        private int nextPrintable() {
            try {
                int ch;
                while (!isPrintable(ch = br.read())) {
                    if (ch == -1) {
                        throw new NoSuchElementException();
                    }
                }

                return ch;
            } catch (IOException e) {
                throw new NoSuchElementException();
            }
        }

        String next() {
            try {
                int ch = nextPrintable();
                StringBuilder sb = new StringBuilder();
                do {
                    sb.appendCodePoint(ch);
                } while (isPrintable(ch = br.read()));

                return sb.toString();
            } catch (IOException e) {
                throw new NoSuchElementException();
            }
        }

        int nextInt() {
            try {
                // parseInt from Integer.parseInt()
                boolean negative = false;
                int res = 0;
                int limit = -Integer.MAX_VALUE;
                int radix = 10;

                int fc = nextPrintable();
                if (fc < '0') {
                    if (fc == '-') {
                        negative = true;
                        limit = Integer.MIN_VALUE;
                    } else if (fc != '+') {
                        throw new NumberFormatException();
                    }
                    fc = br.read();
                }
                int multmin = limit / radix;

                int ch = fc;
                do {
                    int digit = ch - '0';
                    if (digit < 0 || digit >= radix) {
                        throw new NumberFormatException();
                    }
                    if (res < multmin) {
                        throw new NumberFormatException();
                    }
                    res *= radix;
                    if (res < limit + digit) {
                        throw new NumberFormatException();
                    }
                    res -= digit;

                } while (isPrintable(ch = br.read()));

                return negative ? res : -res;
            } catch (IOException e) {
                throw new NoSuchElementException();
            }
        }

        long nextLong() {
            try {
                // parseLong from Long.parseLong()
                boolean negative = false;
                long res = 0;
                long limit = -Long.MAX_VALUE;
                int radix = 10;

                int fc = nextPrintable();
                if (fc < '0') {
                    if (fc == '-') {
                        negative = true;
                        limit = Long.MIN_VALUE;
                    } else if (fc != '+') {
                        throw new NumberFormatException();
                    }
                    fc = br.read();
                }
                long multmin = limit / radix;

                int ch = fc;
                do {
                    int digit = ch - '0';
                    if (digit < 0 || digit >= radix) {
                        throw new NumberFormatException();
                    }
                    if (res < multmin) {
                        throw new NumberFormatException();
                    }
                    res *= radix;
                    if (res < limit + digit) {
                        throw new NumberFormatException();
                    }
                    res -= digit;

                } while (isPrintable(ch = br.read()));

                return negative ? res : -res;
            } catch (IOException e) {
                throw new NoSuchElementException();
            }
        }

        float nextFloat() {
            return Float.parseFloat(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            try {
                int ch;
                while (isCRLF(ch = br.read())) {
                    if (ch == -1) {
                        throw new NoSuchElementException();
                    }
                }
                StringBuilder sb = new StringBuilder();
                do {
                    sb.appendCodePoint(ch);
                } while (!isCRLF(ch = br.read()));

                return sb.toString();
            } catch (IOException e) {
                throw new NoSuchElementException();
            }
        }

        void close() {
            try {
                br.close();
            } catch (IOException e) {
//				throw new NoSuchElementException();
            }
        }
    }
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }

    static class List {
        String Word;
        int length;

        List(String Word, int length) {
            this.Word = Word;
            this.length = length;
        }
    }
    private static class Printer extends PrintWriter {
        Printer(PrintStream out) {
            super(out);
        }
    }
}