Doof on Cartesian Problem Code: CLPNT

You may have helped Chef and prevented Doof from destroying the even numbers. But, it has only angered Dr Doof even further. However, for his next plan, he needs some time. Therefore, Doof has built N$$ walls to prevent Chef from interrupting him. You have to help Chef by telling him the number of walls he needs to destroy in order to reach Dr Doof.

Formally, the whole area can be represented as the first quadrant with the origin at the bottom-left corner. Dr. Doof is located at the origin (0,0)$\mathrm{}\mathrm{}$. There are N$$ walls, the i-th wall is a straight line segment joining the points (ai,0)${}_{}\mathrm{}$ and (0,ai)$\mathrm{}{}_{}$. For every initial position of Chef (xj,yj)${}_{}{}_{}$, find the number of walls he needs to break before reaching Doof. Obviously, chef can't start from a point on the wall. Therefore, if (xj,yj)${}_{}{}_{}$ lies on any of the given walls, print −1$\mathrm{}$ in a new line.

Input

• First line contains T$$, denoting the number of testcases.
• The first line of every test case contains a single integer N$$ denoting the number of walls Dr Doof has built.
• The next line contains N$$ space separated distinct integers each denoting ai${}_{}$.
• The next line contains a single integer Q$$ denoting the number of times Chef asks for your help.
• The next Q$$ lines contains two space separated integers xj${}_{}$ and yj${}_{}$, each denoting the co-ordinates of the starting point of Chef.

Output

For each query, print the number of walls Chef needs to break in order to reach Dr Doof in a separate line. If Chef tries to start from a point on any of the walls, print −1$\mathrm{}$.

Constraints

• 1≤T≤2∗102$\mathrm{}\mathrm{}{\mathrm{}}^{\mathrm{}}$
• 1≤N,Q≤2∗105$\mathrm{}\mathrm{}{\mathrm{}}^{\mathrm{}}$
• 1≤ai≤109$\mathrm{}{}_{}{\mathrm{}}^{\mathrm{}}$
• 0≤xj,yj≤109$\mathrm{}{}_{}{}_{}{\mathrm{}}^{\mathrm{}}$
• a1<a2<a3<....<aN${}_{\mathrm{}}{}_{\mathrm{}}{}_{\mathrm{}}{}_{}$
• Sum of N$$ and Q$$ over all testcases for a particular test file does not exceed 2∗105$\mathrm{}{\mathrm{}}^{\mathrm{}}$

Sample Input

1
2
1 3
5
0 0
2 0
0 4
1 1
1 2

Sample Output

0
1
2
1
-1

Explanation

The sample input can be represented by the graph given below:

If Chef starts from (0,0)$\mathrm{}\mathrm{}$, he can reach Dr Doof without destroying any wall.
If Chef starts from (2,0)$\mathrm{}\mathrm{}$, he has to destroy the 1st$\mathrm{}$ wall.
If Chef starts from (0,4)$\mathrm{}\mathrm{}$, he has to destroy both the walls.
If Chef starts from (1,1)$\mathrm{}\mathrm{}$, he has to destroy the 1st$\mathrm{}$ wall.
As (1,2)$\mathrm{}\mathrm{}$ lies on the second wall, the answer is −1$\mathrm{}$ for the last query.