外传：魔王打工记（四）

在通过搞生态农业大赚一笔后，Home_W现在可谓富可敌国，这辈子再也不用打工了。听说了Home_W的飞黄腾达，不要脸的小晋，立即就从世界另一端，跳回了魔王堡，而且只花了59s。

"主人我是您可爱又能干，跑得还贼快的坐骑啊，您还认识我吗"

"可爱又能干？，你也不撒泡尿照照镜子，不过跑的挺快这点我倒是认同的，看来你大腿应该肉质不错。这样吧，我给你出个问题，如果你能答出来我就让你回归魔王堡，否则我就把你炖了，给我续命"

"主人，我突然想起来家里还有急事，我爷爷生病了，我现在要回家看他，告辞，祝您万寿无疆"

"你上回不是说你爷爷六岁的时候就被一个带着黑框眼镜的人抓去续命了吗？不许跑，给我回来"

说着小晋被抓了起来，关在一个奇怪的世界，这个世界只有两种声音在不断回荡，"WA","TLE"。

而Home_W的题目就显示在天空上：

给n个正整数a1,a2,a3,……，an。问：若将a_L,a_L+1,……a_R的所有连续子序列的gcd求出，并去除重复的gcd后，还会剩下多少个gcd。

其中gcd代表最大公约数，比如gcd(10,5)=5

现在小晋只有1小时的时间能用来答出这题，那么他的命运究竟会何去何从，小A,小C是否能顺利回到地球？欲知后事如何，请参加下次校赛

单组数据

开头是两个整数n,q代表n个数字，q次询问.n,q<=50000

接下来有n个数a1,a2,a3,……an  ,（0<=ai<=10⁹）

再接下来q行，每行包含两个整数L,R. (1<=L<=R<=n)

后台共有4组n=50000,q=50000的大数据，分别用四种算法构造

对于每个查询输出一行，包含一个整数，代表gcd的种类数

10 10
2 9 8 7 5 0 1 6 1 3
1 2
7 7
9 10
2 5
8 10
1 3
1 10
2 8
7 8
7 9

3
1
2
5
3
4
9
7
2
2