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.

Difficulty: interview

Starter code:

Solutions:
def posSearch(arr, num):
 l = 0
 r = len(arr)
 if num < arr[l]:
  return 0
 elif num > arr[r-1]:
  return r
 while l < r:
  m = (l+r)//2
  if arr[m] == num:
   return -1
  if arr[m] < num < arr[m+1]:
   return m+1
  if arr[m] > num:
   r = m
  elif arr[m] < num:
   l = m+1 
 
for _ in range(int(input())):
 n = int(input())
 narr = list(map(int, input().split()))
 q = int(input())
 for i in range(q):
  x, y = list(map(int, input().split()))
  a = x+y
  j = posSearch(narr, a)
  print(j)
   



def binary(arr,s):
 low=0 
 high=n-1
 while low<=high:
  mid=(high+low)//2 
  if arr[mid]<=s:
   ans=mid 
   low=mid +1
  else:
   high=mid-1 
 return ans 



for _ in range(int(input())):
 n=int(input())
 arr=list(map(int,input().split()))
 q=int(input())
 arr.sort()
 for i in range(q):
  x,y=list(map(int,input().split()))
  s=x+y 
  if arr[0]>s:
   print(0)
   continue 
  if arr[0]==s:
   print(-1)
   continue 
  index=binary(arr,s)
  if arr[index]==s:
   print(-1 )
  else:
   print(index+1 )
   
   # TODO: write code...


# cook your dish here
import bisect
test=int(input())
for _ in range(test):
 n=int(input())
 ls=list(map(int,input().split()))
 ls.sort()
 q=int(input())
 for _ in range(q):
  x,y=map(int,input().split())
  z=x+y
  m=bisect.bisect(ls,z)
  if m>0:
   if ls[m-1]==z:
    print(-1)
   else:
    print(m)
  else:
   print(0)

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 q=int(input())
 h=[]
 for i in range(q):
  x,y=list(map(int,input().split()))
  f,c,g=x+y,0,0
  b,m=0,n-1
  while(b<=m):
   i=(b+m)//2
   if l[i]==f:
    g=1
    break
   elif l[i]>f:
    m=i-1
   else:
    b=i+1
  if g==1:
   print(-1)
  else:
   if l[i]>f:
    print(i)
   else:
    print(i+1)
     
  



import sys
from sys import stdin,stdout
from bisect import bisect_right
from os import path

def cinN():return (int(stdin.readline()))
def cin():return(map(int,stdin.readline().split()))



def find_le(a, x):
 'Find rightmost value less than or equal to x'
 i = bisect_right(a, x)
 if i:
  return i-1
 return -1

def func():
 n=cinN()
 l=list(cin())
 #l.sort()
 qn=cinN()
 for _ in range(qn):
  x,y=cin()
  k=x+y
  t=find_le(l,k)
  if t==-1:
   ans=(0)
  else:
   if l[t]==k:
    ans=(-1)
   else:ans=(t+1)
  print(ans)

def __starting_point():
 test=cinN()
 for _ in range(test):func()
__starting_point()

import sys
from sys import stdin,stdout
from bisect import bisect_right
from os import path

def cinN():return (int(stdin.readline()))
def cin():return(map(int,stdin.readline().split()))



def find_le(a, x):
 'Find rightmost value less than or equal to x'
 i = bisect_right(a, x)
 if i:
  return i-1
 return -1

def func():
 n=cinN()
 l=list(cin())
 #l.sort()
 qn=cinN()
 for _ in range(qn):
  x,y=cin()
  k=x+y
  t=find_le(l,k)
  if t==-1:
   ans=(0)
  else:
   if l[t]==k:
    ans=(-1)
   else:ans=(t+1)
  print(ans)

def __starting_point():
 test=cinN()
 for _ in range(test):func()
__starting_point()

import sys
from sys import stdin,stdout
from bisect import bisect_right
from os import path

def cinN():return (int(stdin.readline()))
def cin():return(map(int,stdin.readline().split()))



def find_le(a, x):
 'Find rightmost value less than or equal to x'
 i = bisect_right(a, x)
 if i:
  return i-1
 return -1

def func():
 n=cinN()
 l=list(cin())
 l.sort()
 qn=cinN()
 for _ in range(qn):
  x,y=cin()
  k=x+y
  t=find_le(l,k)
  if t==-1:
   ans=(0)
  else:
   if l[t]==k:
    ans=(-1)
   else:ans=(t+1)
  print(ans)

def __starting_point():
 test=cinN()
 for _ in range(test):func()
__starting_point()

import sys
from sys import stdin,stdout
from bisect import bisect_right
from os import path

if (path.exists('input.txt')):
 #------------------Sublime--------------------------------------#
 sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
 def cinN():return (int(input()))
 def cin():return(map(int,input().split()))
else:
 #------------------PYPY FAst I/o--------------------------------#
 def cinN():return (int(stdin.readline()))
 def cin():return(map(int,stdin.readline().split()))



def find_le(a, x):
 'Find rightmost value less than or equal to x'
 i = bisect_right(a, x)
 if i:
  return i-1
 return -1

def func():
 n=cinN()
 l=list(cin())
 l.sort()
 qn=cinN()
 for _ in range(qn):
  x,y=cin()
  k=x+y
  t=find_le(l,k)
  if t==-1:
   ans=(0)
  else:
   if l[t]==k:
    ans=(-1)
   else:ans=(t+1)
  print(ans)

def __starting_point():
 test=cinN()
 for _ in range(test):func()
__starting_point()

import sys
from sys import stdin,stdout
from bisect import bisect_right
from os import path
#cin=sys.stdin.readline
#cout=sys.stdout.write

if (path.exists('input.txt')):
 #------------------Sublime--------------------------------------#
 sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
 def cinN():return (int(input()))
 def cin():return(map(int,input().split()))
else:
 #------------------PYPY FAst I/o--------------------------------#
 def cinN():return (int(stdin.readline()))
 def cin():return(map(int,stdin.readline().split()))



def find_le(a, x):
 'Find rightmost value less than or equal to x'
 i = bisect_right(a, x)
 if i:
  return i-1
 return -1

def func():
 n=cinN()
 l=list(cin())
 l.sort()
 qn=cinN()
 for _ in range(qn):
  x,y=cin()
  k=x+y
  t=find_le(l,k)
  if t==-1:
   ans=(0)
  else:
   if l[t]==k:
    ans=(-1)
   else:ans=(t+1)
  print(ans)

def __starting_point():
 test=cinN()
 for _ in range(test):func()
__starting_point()

import sys
from sys import stdin,stdout
from bisect import bisect_right
from os import path
#cin=sys.stdin.readline
cout=sys.stdout.write

if (path.exists('input.txt')):
 #------------------Sublime--------------------------------------#
 sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
 def cinN():return (int(input()))
 def cin():return(map(int,input().split()))
else:
 #------------------PYPY FAst I/o--------------------------------#
 def cinN():return (int(stdin.readline()))
 def cin():return(map(int,stdin.readline().split()))



def find_le(a, x):
 'Find rightmost value less than or equal to x'
 i = bisect_right(a, x)
 if i:
  return i-1
 return -1

def func():
 st=''
 n=cinN()
 l=list(cin())
 l.sort()
 qn=cinN()
 for _ in range(qn):
  x,y=cin()
  k=x+y
  t=find_le(l,k)
  if t==-1:
   ans=(0)
  else:
   if l[t]==k:
    ans=(-1)
   else:ans=(t+1)
  print(ans)


def __starting_point():
 test=cinN()
 for _ in range(test):func()
__starting_point()

import sys
from sys import stdin,stdout
from bisect import bisect_right
from os import path
#cin=sys.stdin.readline
cout=sys.stdout.write

if (path.exists('input.txt')):
 #------------------Sublime--------------------------------------#
 sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
 def cinN():return (int(input()))
 def cin():return(map(int,input().split()))
else:
 #------------------PYPY FAst I/o--------------------------------#
 def cinN():return (int(stdin.readline()))
 def cin():return(map(int,stdin.readline().split()))



def find_le(a, x):
 'Find rightmost value less than or equal to x'
 i = bisect_right(a, x)
 if i:
  return i-1
 return -1

def func():
 st=''
 n=cinN()
 l=list(cin())
 l.sort()
 qn=cinN()
 for _ in range(qn):
  x,y=cin()
  k=x+y
  t=find_le(l,k)
  if t==-1:
   ans=(0)
  else:
   if l[t]==k:
    ans=(-1)
   else:ans=(t+1)
  print(ans) 
 #cout(str(ans))

def __starting_point():
 test=cinN()
 for _ in range(test):func()
__starting_point()

import sys
from sys import stdin,stdout
from bisect import bisect_right
from os import path
#cin=sys.stdin.readline
cout=sys.stdout.write

if (path.exists('input.txt')):
 #------------------Sublime--------------------------------------#
 sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
 def cinN():return (int(input()))
 def cin():return(map(int,input().split()))
else:
 #------------------PYPY FAst I/o--------------------------------#
 def cinN():return (int(stdin.readline()))
 def cin():return(map(int,stdin.readline().split()))



def find_le(a, x):
 'Find rightmost value less than or equal to x'
 i = bisect_right(a, x)
 if i:
  return i-1
 return -1

def func():
 st=''
 n=cinN()
 l=list(cin())
 l.sort()
 qn=cinN()
 for _ in range(qn):
  x,y=cin()
  k=x+y
  t=find_le(l,k)
  if t==-1:
   ans=(0)
  else:
   if l[t]==k:
    ans=(-1)
   else:ans=(t+1)
  print(ans)

def __starting_point():
 test=cinN()
 for _ in range(test):func()
__starting_point()

import sys
from sys import stdin,stdout
from bisect import bisect_right
from os import path
#cin=sys.stdin.readline
cout=sys.stdout.write

if (path.exists('input.txt')):
 #------------------Sublime--------------------------------------#
 sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
 def cinN():return (int(input()))
 def cin():return(map(int,input().split()))
else:
 #------------------PYPY FAst I/o--------------------------------#
 def cinN():return (int(stdin.readline()))
 def cin():return(map(int,stdin.readline().split()))



def find_le(a, x):
 'Find rightmost value less than or equal to x'
 i = bisect_right(a, x)
 if i:
  return i-1
 return -1

def func():
 st=''
 n=cinN()
 l=list(cin())
 l.sort()
 qn=cinN()
 for _ in range(qn):
  x,y=cin()
  k=x+y
  t=find_le(l,k)
  if t==-1:
   ans=(0)
  else:
   if l[t]==k:
    ans=(-1)
   else:ans=(t+1)
  print(ans)
  #st='\n'.join((st,str(ans)))
 #print(st)
 #cout('\n')
def __starting_point():
 test=cinN()
 for _ in range(test):func()
__starting_point()


from collections import defaultdict
import os
import sys
from io import BytesIO, IOBase


def binarySearchCount(arr, n, key): 
 
 left = 0
 right = n - 1
 
 count = 0
 
 while (left <= right):  
  mid = int((right + left) / 2) 
 
  # Check if middle element is 
  # less than or equal to key 
  if (arr[mid] <= key):  
 
   # At least (mid + 1) elements are there 
   # whose values are less than 
   # or equal to key 
   count = mid + 1
   left = mid + 1
   
  # If key is smaller, ignore right half 
  else: 
   right = mid - 1
  
 return count 
def can_break(N,a,d,x,y,maxi,mini):
 c=x+y
 if c<mini:
  return 0
 if c in d:
  return -1
 
 if c>maxi:
  return N 
 
 x=binarySearchCount(a,N,c)
 return x
 """
    mid=(N-1)//2
    if c<a[mid]:
     count=0
     for i in a:
      if i>c:
       return count
      count+=1
  
    else:
     count=mid+1
     for i in range(mid+1,N):
      if a[i]>c:
       return count
      count+=1
    """ 

T=int(input())
while T:
 N=int(input())
 a=tuple(map(int,input().split()))
 d=defaultdict()
 mini=a[0]
 maxi=a[-1]
 for i in range(N):
  d[a[i]]=i
 Q=int(input())
 while Q:
  x,y=list(map(int,input().split()))
  if x==0 and y==0:
   print(0)
  else:
   print(can_break(N,a,d,x,y,maxi,mini))
  Q-=1
 T-=1 


import bisect

for i in range(int(input())):
 n = int(input())
 a = [int(x) for x in input().split()]
 a.sort()
 for j in range(int(input())):
  x, y = map(int, input().split())
  z = x + y
  nu = bisect.bisect(a, z)
  if nu > 0:

   if a[nu - 1] == z:
    print(-1)
   else:
    print(nu)
  else:
   print(0)

from bisect import bisect
for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 c=[]
 for _ in range(int(input())):
  x,y=map(int,input().split())
  s=x+y
  st=0
  end=n-1
  t=True
  while(st<=end):
   half=(end+st)//2
   if (l[half]==s):
    t=False
    break
   elif(l[half]>s):
    end=half-1
   else:
    st=half+1
  print(bisect(l,s) if t else -1)