SevenFireflie has a sequence of positive integers with a length of and quickly calculates all the factors of each number. In order to exercise his factor calculation ability, he has selected consecutive subsequences from the sequence and found a positive integer greater than 1 for each subsequence, so that can divide as many numbers in this subsequence as possible. He has also found that 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  (), indicating that there is  test cases next. 
The first line of each test cases has two positive integers  ()， ().
Next line  integers  (), which representing the numbers in this sequence. The two adjacent numbers are separated by a space.
Each of the next  lines contains integers  (), representing a subsequence being queried, , and  are separated by a space.
The input guarantees that the sum of  does not exceed  and the sum of  does not exceed .

输出描述:

For each test case, output  lines, each line 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