408867: GYM103366 G Magic Number Group

Tsiying has a sequence of positive integers with a length of $$$n$$$ and quickly calculates all the factors of each number. In order to exercise his factor calculation ability, he has selected $$$q$$$ consecutive subsequences from the sequence and found a positive integer $$$p$$$ greater than $$$1$$$ for each subsequence, so that $$$p$$$ can divide as many numbers in this subsequence as possible. He has also found that $$$p$$$​ may have more than one.

So the question is, how many numbers in each subsequence can be divided at most?

The first line contains an integer $$$T$$$ ($$$1 \le T \le 5 \times 10 ^ 4$$$), indicating that there is $$$T$$$​​ test cases next.

The first line of each test cases has two positive integers $$$n$$$​ ($$$1\le n\le 5\times10^4$$$​), $$$q$$$ ($$$1\le q\le 5\times10^4$$$)​​​.

Next line $$$n$$$ integers $$$a_i$$$ ($$$1\le i\le n,1\le a_i\le 1\times10^6$$$), which representing the numbers in this sequence. The two adjacent numbers are separated by a space.

Each of the next $$$q$$$ lines contains two integers $$$l,r$$$ ($$$1\le l\le r\le n$$$), representing a subsequence being queried, $$$a_l, a_{l+1}, \cdots, a_r$$$, and $$$l,r$$$ are separated by a space.

The input guarantees that the sum of $$$n$$$​ does not exceed $$$5\times10^4$$$​ and the sum of $$$q$$$​ does not exceed $$$5\times10^4$$$​.

For each test case, output $$$q$$$ lines, each line contains a positive integer, indicating the answer.

1
10 5
20 15 6 1 21 12 2 3 17 9
1 4
2 5
3 6
4 7
5 10

2
3
3
2
4