For a sequence of positive integers where , let be the answer to the following problem:
Among the positive integers , paint at least one and at most of them red, and paint the rest blue. Let be the greatest common divisor (GCD) of the integers painted red, and be the GCD of the integers painted blue. Find the maximum possible value of .
You are given a sequence of positive integers . You will also be given queries. For each query, you will be given two integers and such that . For each query, let , and find .
输入格式
The input is given in the following format:
for all
for all
输出格式
Print lines. On the -th line (), output the answer to the -th query.
