Find the greatest common divisor between two integers and that is in a given range from to (inclusive), i.e. . It is possible that there is no common divisor in the given range.
You will be given the two integers and , then queries. Each query is a range from to and you have to answer each query.
The first line contains two integers and . The second line contains the number of queries . Then lines follow, each line contains one query consisting of two integers and .
Print lines. The -th of them should contain the result of the -th query. If there is no common divisor in the given range for the query, print .