B'Iva and Pav are a famous Serbian competitive programming couple. In Serbia, they call Pav "papuca" and that 's why he will make all of Iva 's wishes come true. Iva gave Pav an array a of n elements. Let 's define f(l, r) = a_l & a_{l+1} & ... & a_r (here & denotes the bitwise AND operation). Note that f(l, r) is not defined when l>r . Iva also gave Pav q queries. Each query consists of 2 numbers, k and l , and she wants Pav to find the largest index r ( l <= r <= n ), such that f(l, r) ge k . Pav wants to solve this problem fast because he doesn 't want to upset Iva. He needs your help. The first line contains a single integer t ( 1 <= t <= 10^4 ) -- the number of test cases. The first line of each test case contains a single integer n ( 1 <= n <= 2 cdot 10^5 ) -- the length of array a . The second line of each test case contains n integers a_1, a_2, ... , a_n ( 1 <= a_i <= 10^9 ) -- the elements of array a . The third line of each test case contains a single integer q ( 1 <= q <= 10^5 ) -- the number of queries Iva gave Pav. The next q lines of each test case contains two numbers, l and k ( 1 <= l <= n , 1 <= k <= 10^9 ) -- the left bound for the subsegment, and the integer k described in statement. It is guaranteed that the sum of n over all test cases does not exceed 2 cdot 10^5 . Also, it is guaranteed that the sum of q over all test cases does not exceed 2 cdot 10^5 . For each query output maximal index r ( l <= r <= n ) such that a_l & a_{l+1} & ... & a_r ge k . If such r doesn 't exist, output -1 . In the first test case n=5 , and the array a = [15, 14, 17, 42, 34] The first query asks for the biggest index r such that the f(1, r) ge 7 . f(1,1) = 15, f(1, 2) = 14,'...