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 static java.lang.Math.*;
import java.util.*;
import java.io.*;
import java.math.BigInteger;

public class _67C {

    public void solve() throws Exception {
        int a=nextInt(), b=nextInt();
        int gcd = new BigInteger(a+"").gcd(new BigInteger(b+"")).intValue();
        LinkedList<Integer> ll = new LinkedList<Integer>();
        for (int i=1; i<=sqrt(gcd)+1; i++)
            if (gcd%i==0) {ll.add(i); ll.add(gcd/i);}
        
        int[] tmp = new int[ll.size()];
        int pos=0;
        for (Integer i: ll) tmp[pos++]=i;
        Arrays.sort(tmp);
        debug(tmp);
        
        int n = nextInt();
        while (n-->0) {
            int lo=nextInt(); int hi=nextInt();
            int f = Arrays.binarySearch(tmp, hi);
            if (f>=0) println(hi);
            else {
                f = -f-2;
                if (f<0 || tmp[f]<lo) {println(-1); continue;}
                else println(tmp[f]);
            }
        }   
    }
    
    

    ////////////////////////////////////////////////////////////////////////////    

    double EPS = 1e-7;
    int INF = Integer.MAX_VALUE;
    long INFL = Long.MAX_VALUE;
    double INFD = Double.MAX_VALUE;

    int[] dx = {0,1,0,-1};
    int[] dy = {-1,0,1,0};
    int[] dx8 = {0,1,1,1,0,-1,-1,-1};
    int[] dy8 = {-1,-1,0,1,1,1,0,-1};
    int[] knightMovesX = {1,2,2,1,-1,-2,-2,-1};
    int[] knightMovesY = {-2,-1,1,2,2,1,-1,-2};

    class Point {
        int x,y;
        public Point(int xx, int yy) {
            x=xx; y=yy;
        }
        public double dist(Point p) {
            return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));
        }
    }
    class PointL {
        long x,y;
        public PointL(long xx, long yy) {
            x=xx; y=yy;
        }
        public double dist(PointL p) {
            return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));
        }
    }
    class PointD {
        double x,y;
        public PointD(double xx, double yy) {
            x=xx; y=yy;
        }
        public double dist(PointD p) {
            return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));
        }
    }
    double dist(int x, int y, int xx, int yy) {
        return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));
    }
    double dist(long x, long y, long xx, long yy) {
        return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));
    }
    double dist(double x, double y, double xx, double yy) {
        return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));
    }


    @SuppressWarnings("serial")
    class IncMap extends HashMap<Object, Integer> {
        boolean add(Object key, int amount) {
            Integer i = get(key);
            if (i!=null) {
                put(key, i+amount);
                return false;
            } else {
                put(key, amount);
                return true;
            }
        }
        boolean add(Object key) {
            return add(key, 1);
        }
    }
    

    int min(int... nums) {
        int r = INF;
        for (int i: nums)
            if (i<r) r = i;
        return r;
    }
    int max(int... nums) {
        int r = -INF;
        for (int i: nums)
            if (i>r) r = i;
        return r;
    }
    long minL(long... nums) {
        long r = INFL;
        for (long i: nums)
            if (i<r) r = i;
        return r;
    }
    long maxL(long... nums) {
        long r = -INFL;
        for (long i: nums)
            if (i>r) r = i;
        return r;
    }
    long partsFitCnt(long partSize, long wholeSize) {
        return (partSize+wholeSize-1)/partSize;
    }
    
    int digitSum(long i) {
        i = abs(i);
        int r = 0;
        while (i>0) {
            r+=i%10;
            i/=10;
        }
        return r;
    }
    long digitProd(long i) {
        if (i==0) return 0;
        i = abs(i);
        long r = 1;
        while (i>0) {
            r*=i%10;
            i/=10;
        }
        return r;
    }
    
    double log_2 = log(2);
    double log2(double i) {
        return log(i)/log_2;
    }
    long binpow(int x, int n) {
        long r = 1;
        while (n>0) {
            if ((n&1)!=0) r*=x;
            x*=x;
            n>>=1;
        }
        return r;
    }
    long fac(int i) {
        if (i>20) throw new IllegalArgumentException();
        return i<=1 ?  1:fac(i-1)*i;
    }
    
    boolean isPalindrome(String s) {
        for (int i=0; i<s.length()/2; i++)
            if (s.charAt(i)!=s.charAt(s.length()-1-i)) return false;
        return true;
    }
    
    
    int[] months = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    boolean isLeapYear(int y) {
        return y%4==0 && (y%400==0 || y%100!=0);
    }
    boolean isValidDate(int d, int m, int y) {
        if (isLeapYear(y) && m==2 && d==29) return true;
        return m>0 && m<=12 && d>0 && d<=months[d];
    }
    int[] nextDay(int d, int m, int y) {
        if (d>=months[m])
            if (m==2 && d==28 && isLeapYear(y)) d++;
            else {d=1; m++;}
        else
            d++;
        if (m==13) {d=1; m=1; y++;}
        return new int[] {d,m,y};
    }


    long timer = System.currentTimeMillis();
    void startTimer() {
        timer = System.currentTimeMillis();
    }
    void stopTimer() {
        System.err.println("time: "+(System.currentTimeMillis()-timer)/1000.0);
    }


    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

    String nextLine() throws IOException {
        return in.readLine();
    }
    String nextWord() throws IOException {
        StringBuilder sb = new StringBuilder();
        int c = 0;
        while (c<=' ') c=in.read();
        while (c>' ') {
            sb.append((char)c);
            c = in.read();
        }
        return sb.toString();
    }
    int nextInt() throws NumberFormatException, IOException {
        return Integer.parseInt(nextWord());
    }
    long nextLong() throws NumberFormatException, IOException {
        return Long.parseLong(nextWord());
    }
    double nextDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(nextWord());
    }

    void print(Object o) throws IOException {
        out.write(o.toString());
    }
    void println(Object o) throws IOException {
        out.write(o.toString());
        out.newLine();
    }
    void print(Object... o) throws IOException {
        for (int i=0; i<o.length; i++) {
            if (i!=0) out.write(' ');
            out.write(o[i].toString());
        }
    }
    void println(Object... o) throws IOException {
        print(o);
        out.newLine();
    }
    void printArr(int[] arr) throws IOException {
        for (int i=0; i<arr.length; i++) {
            if (i!=0) out.write(' ');
            out.write(Integer.toString(arr[i]));
        }
    }
    void printArr(long[] arr) throws IOException {
        for (int i=0; i<arr.length; i++) {
            if (i!=0) out.write(' ');
            out.write(Long.toString(arr[i]));
        }
    }
    void printArr(double[] arr) throws IOException {
        for (int i=0; i<arr.length; i++) {
            if (i!=0) out.write(' ');
            out.write(Double.toString(arr[i]));
        }
    }
    void printlnArr(int[] arr) throws IOException {
        printArr(arr);
        out.newLine();
    }
    void printlnArr(long[] arr) throws IOException {
        printArr(arr);
        out.newLine();
    }
    void printlnArr(double[] arr) throws IOException {
        printArr(arr);
        out.newLine();
    }

    void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }

    public static void main(String[] args) throws Exception {
        Locale.setDefault(Locale.US);
        new _67C().solve();
        out.flush();
        out.close(); in.close();
    }
}