题目描述

给定一个长度为 $n$ 的非负整数数组，以及 $m$ 个询问。每个询问由两个数 $l$ 和 $r$ 组成。

对于每个询问，请求出子数组 $[l,r]$ 中所有两两最大公约数的最大值，也就是：

输入格式

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示数组大小。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^6$），表示数组元素。

第三行包含一个整数 $m$（$1 \le m \le 2 \cdot 10^5$），表示询问个数。

接下来 $m$ 行，第 $i$ 行包含两个整数 $l_i,r_i$（$1 \le l_i < r_i \le n$），表示询问区间的边界。

输出格式

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

输入

3
2 3 6
3
1 2
2 3
1 3

输出

1
3
3

计分方式

1. （$12$ 分）$m,n,a_i \le 200$；
2. （$7$ 分）$m,n \le 200$；
3. （$17$ 分）$a_i \le 50$；
4. （$7$ 分）所有 $a_i$ 都是 $2$ 的幂；
5. （$27$ 分）$m,n \le 15000$；
6. （$13$ 分）$m,n \le 35000$；
7. （$17$ 分）无额外限制。