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.
The first line contains two integers a and b (1≤a,b≤109). The second line contains the number of queries n (1≤n≤104). Then n lines follow, each line contains one query consisting of two integers low and high (1≤low≤high≤109).
Print n lines. The i-th of them should contain the result of the i-th query. If there is no common divisor in the given range for the query, print −1.