给你一个长度为 $n$ 的序列 $a$，你需要回答 $q$ 个询问：

给定两个整数 $l$ 和 $r$，求 $\gcd(a_i, a_j)$ 的最大值，其中 $l \le i < j \le r$。

$\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数（GCD）。

输入格式

本题包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

第一行包含两个整数 $n, q$（$2 \le n \le 10^5$，$1 \le q \le 10^5$）。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le n$）。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l < r \le n$），表示一个询问。

保证 $\sum n \le 10^6$，$\sum q \le 10^6$。

输出格式

对于每个询问，输出一行，包含一个整数，表示该询问的答案。

样例

输入样例 1

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

输出样例 1

1
2
2