B. Convarge To 1
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Zaher has an array $$$a$$$ of $$$n$$$ integers, one day Zaher decided to make a challenge to the students in his math class.

At first, Zaher repeats the following operation on the array in front of his students until all the elements in the array are equal to one.

Each operation has two steps:

  1. Choose the maximum number from the array $$$a$$$, let it be $$$a_i$$$ (if there are multiple numbers equal to the maximum, choose the number with the lowest index).
  2. Divide $$$a_i$$$ by the largest prime number that divides it.

Then the challenge can be represented by $$$q$$$ questions. In each question, Zaher will give his students two numbers, $$$l$$$ and $$$r$$$, and the students should know the first time that all elements of the subarray $$$[a_l, a_{l+1}, .., a_r]$$$ become equal to $$$1$$$.

The students in the math class are not able to solve all of Zaher's questions, help them to find the answers.

Input

The first line contains one integer $$$n$$$ $$$( 1 \le n, q \le 2 \cdot 10^{6} )$$$ — the length of the array $$$a$$$ and the number of questions respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, .., a_n$$$ $$$( 1 \le a_i \le 2 \cdot 10^{6} )$$$ — Zaher's array.

The next $$$q$$$ lines contain two integers $$$l_i, r_i$$$ $$$( 1 \le l_i \le r_i\le n )$$$ — the numbers that Zaher gave to his students in the $$$i$$$-th question.

Output

Output $$$q$$$ lines, the $$$i$$$-th line should contain the first time that all elements of the array $$$[a_l, a_{l+1}, .., a_r]$$$ equal to $$$1$$$.

Examples
Input
3 2
4 6 5
1 3
1 2
Output
5
5
Input
6 6
12 22 5 7 25 8
1 3
1 6
2 5
2 6
3 5
4 6
Output
11
12
11
12
7
12
Note

Description of the first testcase:

Applying Zaher's operations done as follows:

Firstly we choose $$$6$$$ since it's the largest element in the array and divide it by its largest prime factor which is $$$3$$$, and get the array: $$$[4, 5, 2]$$$.

Secondly, we choose the $$$5$$$ since it's the largest number and divide it by its largest factor and get the array $$$[4, 1, 2]$$$.

Third, we choose $$$4$$$ and divide it by $$$2$$$ and get the array $$$[2, 1, 2]$$$.

Fourth we choose $$$2$$$ (first one) and divide it by $$$2$$$ and get the array $$$[1, 1, 2]$$$.

Fifth we choose $$$2$$$ and divide it by $$$2$$$ and get the array $$$[1, 1, 1]$$$.

In the first query: the array becomes all equal to $$$1$$$ after $$$5$$$ operations.

In the second query: the subarray $$$[a_1, a_2]$$$ become all equal to $$$2$$$ after $$$4$$$ operations.