锘? Description

?Time Limit: 3000 MS Memory Limit: 65536 K


Description

给你一个序列长度为,每次询问,给出l,r,求[l,r]区间内所有子区间的gcd最大值。

即:给出l,r,求所有 中的最大值,其中

“您认为我们这样瞎扯淡的来来去去可以继续到何时?”她问。
CaCO3早在五十三年七个月零十一个日日夜夜之前就准备好了答案。
“永生永世!”他说。

Input

第1行为组数T.

接下来T组,每组包含M+2行。

第一行为两个数, 分别表示子序列长度以及询问次数。其中

第二行为个数,其中

接下来行,每行包括两个数,代表一次询问,其中

Output

对于每个询问输出相应的答案。

Sample Input

1

4 2

2 2 4 4

1 2

2 3

Sample Output

2

4

Note

样例解释:

对于第一个询问,

其中[1,2]区间,包含[1,1]区间,[2,2]区间,[1,2]区间,区间gcd分别为2,2,2,答案为2。