给我们一个长度为n的整数序列a: a₁,a₂,…,a_i,…,a_n,定义f(l,r)如下：

F(l,r)=a_l&a_l+1&a_l+2&…&a_r （显然，l应该不大于r，&为位与运算符）

现向我们发出q次询问，每次询问给我们两个值：k和l，请你帮忙找出最大的r（r>=l）值,使得f(l,r)>=k成立。

       第一行包含一个整数t(1≤t≤1e4)——测试用例的数量。

对于每个测试用例：

第一行一个整数n（1<=n<=2e5）:整数序列a的长度；

第二行共n个整数a₁,a₂,…,a_i,…,a_n（1<=a_i<=1e9），为序列a的n个元素。

第三行一个整数q（1<=q<=1e5），为询问次数。

接下来共q行，对应q次询问，每行两个整数l和k（1≤l≤n, 1≤k≤1e9）：l为子序列的左边界，k值见题中描述。

保证所有测试用例的 n 之和与 q 之和均不超过 2e5 。

       输出共t行，每个测试用例一行。

对于每个测试用例，共输出q个整数（空格隔开），第i个整数为第i次询问时候能够球的的最大整数r（l<=r<=n）: r为满足F(l,r)>=k的最大右边界值。特别提醒，如果不存在满足要求的r值，则输出：-1。