题目背景

难道说...
这么说来...给珂朵莉她们...
正给珂朵莉带来痛苦的是...

【威廉？】
【威廉，说真的，你到底怎么了？】
【出什么事了？】
【啊...】
你不慌张吗
【别看我这样，其实我心脏确实有在猛跳】
【但是呢，虽然我不知道发生了什么事】

【可一直爱逞强的你，难得会对我露出软弱的一面嘛~】
【高兴的心情，还有希望你打起精神的心情加在一起】
【要远远胜过惊慌的情绪】

你...
【你刚才，流露着一副要是没人管你就会自己消失的表情哦？】
【虽然非常难为情，但我实在不能撇下你】

你是个...好女人啊...

【抱歉，我没有听清楚，再说一遍】
没什么啦...

【啊...你还死撑】
【再说一遍，再说一遍就好】
和我结婚吧

【不对...嗯？】
我终于找到了
找到了渴望去保护的人
找到了渴望回去的归宿
觉得自己还可以继续生存下去
总算真切地认识到自己还有继续生存的价值和资格
所以...
我要给你幸福

【嗯】
【我也不会离开你身边的】
【永远，永远和你在一起哦】

题目描述

珂朵莉给你了一个长为 $n$ 的序列，有 $m$ 次查询，每次查询一段区间的乘积的约数个数 $\bmod 19260817$ 的值。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数表示这个序列 $a_i$。

之后 $m$ 行，每行两个整数 $l,r$ 表示查询的区间

输出格式

$m$ 行，每行输出一个整数表示答案

5 5
64 2 18 9 100
1 5
2 4
2 3
1 4
3 4

165
15
9
45
10

提示

Idea：will7101，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477

$1\leq n,m\leq 10^5$，$1 \leq a_i \leq10^9$。