Zulu is a nature lover kind of boy. He visits forests, natural parks and other scenic places regularly. While one of his visit to a bird's park, a problem came in his mind. Suppose, there are N birds present in the park. Each of the bird is rotating around a circular pillar present in the middle of the park. We are provided with the time periods $(T[i])$ for each bird. Time period is defined as the time needed to complete a full rotation around the pillar.

Consider that each bird starts its rotation from a fixed point i.e. where Zulu is sitting. Now, Zulu wants to know about the number of birds which are going to be present at that spot at any given time. Since Zulu is a naughty child, he won't give you a fixed time instant instead he gives a range of time and wants you to calculate the maximum number of birds at any integral time instant within that range. To further complicate the question, he is going to give you multiple queries also.

Input :

First line of input will contain $TEST$ denoting number of test cases. For each test case, First line will contain N denoting number of birds. In the second line N numbers will be given representing time periods $(T[i])$ for each of the bird. In next line Q will be given which corresponds to number of queries asked. Below this there will be Q lines given each having two integers X & Y which refer to the start time and end time of the given query.

Output :

For each of the query, output the maximum number of birds in a separate line.

Constraints :

$1 \le$ $TEST$ $\le 5$

$1 \le N, Q, X, Y \le 2*10^5$

$1 \le T[i] \le 10^{9}$

$X \le Y$