题目背景

题目描述

你是 ACE。

你有一个整数数列 $a_1,a_2,\cdots,a_n$。

你需要解决 $m$ 个询问，每个询问会给定 $l,r$，你需要回答以下问题：

对于下标在 $l\sim r$ 之间的子序列（共 $2^{r-l+1}$ 个），写出所有子序列的乘积（空序列为 $1$），这些乘积中，最小的没有出现的正整数是多少。

一个数列的子序列是删除若干元素后得到的数列。

输入格式

第一行一个整数 $T$ 表示数据组数。

每组数据的第一行为两个正整数 $n,m$。

第二行为 $n$ 个正整数 $a_1,a_2,\cdots,a_n$。

接下来 $m$ 行，每行有两个整数 $l,r$，表示询问。

输出格式

对于每组数据，输出 $m$ 行，每行一个整数表示答案。

样例一

input

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

output

3
4
7

样例二

见下发文件中的 ace/ex_ace2.in 以及 ace/ex_ace2.ans。

样例三

见下发文件中的 ace/ex_ace3.in 以及 ace/ex_ace3.ans。

限制与约定

对于 $100\%$ 的数据，$1\le T\le 5$，$1\le n,m\le 10^5$，$1\le a_i\le 10^9$，$1\le l\le r\le n$。