T454251 「2024 百度之星选拔赛」伏瓦鲁魔法图书馆

帕秋莉有 $n$ 本魔导书，她将这 $n$ 本魔导书排成一排。 每本魔导书有一个魔力值 $a_i$，魔力值是一个正整数。 帕秋莉现在有 $q$ 次询问，每次询问一个连续子区间 $[l, r]$ ，对于每次询问需要找到一个大于 $1$ 的正整数 $p$ ，使得 $p$ 可以整除这个子区间中尽可能多的魔力值 $a_i$ $\;$ ($l \le i \le r$)。 帕秋莉想要知道，对于每次询问的子区间 $[l, r]$，找到一个大于 $1$ 的正整数 $p$ 最多可以整除数字的数量。

**有多组测试数据** 第一行包含一个整数 $T$ $\;$ ($1 \le T \le 5\times 10^4$)，表示测试数据组数。 对于每组测试数据： 第一行包含两个整数 $n, q$ $\;$ ($1 \le n \le 5\times 10^4$, $1 \le q \le 5 \times 10^4$)，分别表示魔导书个数和询问次数。 第二行包含 $n$ 个整数 $a_i$ $\;$ ($1 \le a_i \le 10^6$, $1\le i \le n$)，表示每本魔导书的魔力值。 接下来 $q$ 行每行包含两个整数 $l, r$ $\;$ ($1 \le l \le r \le n$)，表示询问的区间 $[l, r]$，也就是连续子序列 $a_l, a_{l + 1} \ldots , a_{r}$。 保证所有测试数据满足 $\sum n \le 5 \times 10^4, \sum q \le 5 \times 10^4$。

对于每组测试数据： 输出 $q$ 行，每行一个整数，表示每次询问的子区间最多可以整除多少个数字。

### 样例解释 第一次询问子区间 $[1, 4]$，可以选择一个正整数 $2$，其中 $20, 15, 2$ 可以被整除，故答案为 $3$； 第二次询问子区间 $[2, 5]$，可以选择一个正整数 $3$，其中 $15, 6， 33$ 可以被整除，故答案为 $3$； 第三次询问子区间 $[3,7]$，可以选择一个正整数 $2$，其中 $6, 2， 12， 24$ 可以被整除，故答案为 $4$； 第四次询问子区间 $[8,10]$，可以选择一个正整数 $3$，其中 $27, 9$ 可以被整除，故答案为 $2$。