Description

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

Input Format

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

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

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

Output Format

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

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

165
15
9
45
10

Hint

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

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