Description

Chtholly gives you a sequence of length $n$. There are $m$ queries. For each query, you need to compute the number of divisors of the product of a subarray, taken $\bmod 19260817$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers, representing the sequence $a_i$.

Then follow $m$ lines, each containing two integers $l, r$, representing the queried interval.

Output Format

Output $m$ lines. Each line contains one integer, the answer to the corresponding query.

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.

Constraints: $1 \leq n, m \leq 10^5$, $1 \leq a_i \leq 10^9$.

Translated by ChatGPT 5