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)$. There are $N$ walls, the i-th wall is a straight line segment joining the points $(a_i, 0)$ and $(0, a_i)$. For every initial position of Chef $(x_j, y_j)$, 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 $(x_j, y_j)$ lies on any of the given walls, print $-1$ 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 $a_i$.
- 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 $x_j$ and $y_j$, 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$.

-----Constraints-----
- $1 \leq T \leq 2 * 10^2$
- $1 \leq N, Q \leq 2 * 10^5$
- $1 \leq a_i \leq 10^9$
- $0 \leq x_j, y_j \leq 10^9$
- $a_1 < a_2 < a_3 < .... < a_N$
- Sum of $N$ and $Q$ over all testcases for a particular test file does not exceed $2 * 10^5$

-----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)$, he can reach Dr Doof without destroying any wall.

If Chef starts from $(2, 0)$, he has to destroy the $1st$ wall.

If Chef starts from $(0, 4)$, he has to destroy both the walls.

If Chef starts from $(1, 1)$, he has to destroy the $1st$ wall.

As $(1, 2)$ lies on the second wall, the answer is $-1$ for the last query.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '\nfrom collections import defaultdict\nimport os\nimport sys\nfrom io import BytesIO, IOBase\n\n\ndef binarySearchCount(arr, n, key): \n \n left = 0\n right = n - 1\n \n count = 0\n \n while (left <= right):  \n  mid = int((right + left) / 2) \n \n  # Check if middle element is \n  # less than or equal to key \n  if (arr[mid] <= key):  \n \n   # At least (mid + 1) elements are there \n   # whose values are less than \n   # or equal to key \n   count = mid + 1\n   left = mid + 1\n   \n  # If key is smaller, ignore right half \n  else: \n   right = mid - 1\n  \n return count \ndef can_break(N,a,d,x,y,maxi,mini):\n c=x+y\n if c<mini:\n  return 0\n if c in d:\n  return -1\n \n if c>maxi:\n  return N \n \n x=binarySearchCount(a,N,c)\n return x\n """\n    mid=(N-1)//2\n    if c<a[mid]:\n     count=0\n     for i in a:\n      if i>c:\n       return count\n      count+=1\n  \n    else:\n     count=mid+1\n     for i in range(mid+1,N):\n      if a[i]>c:\n       return count\n      count+=1\n    """ \n\nT=int(input())\nwhile T:\n N=int(input())\n a=tuple(map(int,input().split()))\n d=defaultdict()\n mini=a[0]\n maxi=a[-1]\n for i in range(N):\n  d[a[i]]=i\n Q=int(input())\n while Q:\n  x,y=list(map(int,input().split()))\n  if x==0 and y==0:\n   print(0)\n  else:\n   print(can_break(N,a,d,x,y,maxi,mini))\n  Q-=1\n T-=1 \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14431