This question is not from Cf or somewhere else. If you found any questions that match it by coincidence, it would be really helpful if you shared them.

I was trying to make a question mixed with pre-computing and gcd. Brute Force may be applied. But I cannot find another way to solve the bigger constraints. Help needed.

Time limit per test: 2 seconds 
memory limit per test: 265 megabytes 

Anish found a magical number in the dark forest. Becoming greedy, he made a lot of numbers with it.

let the magical number be x .

You are given an array that Anish made. Where the i th number is

ai = x * n ; where n is an arbitrary integer ( possibly 0 )

Now, print the maximum possible number Anish could have found. and,

You will be given q queries. Each query consists of 2 indices, i and j. For each query, print the maximum number required to make the numbers within the interval [i, j] in that array.

Input:

The first line contains a single integer t, the number of test cases. (1 <= t <= 1000)

Each test case consists of:

1. An integer n — size of the array (1 <= n <= 100,000)

1. n integers a1, a2, …, an (1 <= ai <= 10^9)

1. An integer q — number of queries (1 <= q <= 100,000)

1. q lines, each containing two integers i and j . (1 <= i <= j <= n)

Sum of all n over all test cases ≤ 2×10^5

Sum of all q over all test cases ≤ 2×10^5.

Output:

For each test case:

1. Print a single integer: maximum possible number Anish could have found . (for the whole array)

1. Next q lines: for each query, print the maximum possible number to make the numbers in that subarray [i, j]

Example:

Input:

1
4
7 15 30 39
3
2 3
2 4
1 3

Output:

1
15
3
1