Preparing NOJ # Magic Number Group

1000ms 262144K

## Description:

SevenFireflie 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?

## Input:

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$​.

## Output:

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

## Sample Input:

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


## Sample Output:

2
3
3
2
4


Info Provider CodeForces Gym

Code GYM103366G

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/25/2021 22:31:57

Related

Nothing Yet