You are given an array $a$ of length $n$.

We define the value of an interval $[l, r]$ as

$$\max_{\substack{l \le i < j < k \le r \\ j-i \le k-j}} \gcd(a_i, a_j, a_k)$$

If $r - l \le 1$, the value is $0$.

There will be $q$ queries. In each query, you need to find the value of a particular interval.

Input

The first line contains two integers $n$ and $q$ ($3 \le n \le 1.5 \times 10^5$, $1 \le q \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$).

Each of the next $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$).

Output

For each query, output one line, an integer, the value of the interval.

Examples

Input 1

8 8
8 24 4 6 6 7 3 3
1 5
2 6
3 7
5 8
4 8
1 3
2 5
3 8

Output 1

4
2
3
1
3
4
2
3