408867: GYM103366 G Magic Number Group
Description
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?
InputThe 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$$$.
OutputFor each test case, output $$$q$$$ lines, each line contains a positive integer, indicating the answer.
ExampleInput1 10 5 20 15 6 1 21 12 2 3 17 9 1 4 2 5 3 6 4 7 5 10Output
2 3 3 2 4